Exercise IX
Consider the (singly) linked list data structure (as it was described in an earlier chapter). We define the following operations:
- insert front: insert a element to the front of a linked list (prepend the list). This is not updating the value of an existing element.
- insert middle: insert an element at a random index at a random index $i$ where $0 < i < \text{length} - 1$
- insert back: insert an element to the end of the list (append the list). assume you have only a pointer to the front of the list.
- corresponding delete operations (delete front, delete middle, delete back).
- access read the data stored in a node at a random position.
Exercise Based on your understanding of the linked list data structure, complete the following table. Use Big-Oh notation for expressing asymptotic runtime.
| Operation | Asymptotic runtime |
|---|---|
| insert front | |
| insert middle | |
| insert back | |
| delete front | |
| delete middle | |
| delete back | |
| access |
Solution
| Operation | Asymptotic runtime |
|---|---|
| insert front | $O(1)$ — dereference the head pointer |
| insert middle | $O(n)$ — reach the element before target position |
| insert back | $O(n)$ — reach the last element |
| delete front | $O(1)$ — update the head pointer |
| delete middle | $O(n)$ — reach the element before target position |
| delete back | $O(n)$ — reach the last element |
| access | $O(n)$ — reach the target element |