Exercise IX
- Use Big-Oh notation to describe the asymptotic running time of the operations of the data structures we have implemented so far.
Consider the (singly) linked list data structure (as it was described in an earlier chapter). Then, 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 | $\Omicron(1)$ — dereference the head pointer |
| insert middle | $\Omicron(n)$ — reach the element before target position |
| insert back | $\Omicron(n)$ — reach the last element |
| delete front | $\Omicron(1)$ — update the head pointer |
| delete middle | $\Omicron(n)$ — reach the element before target position |
| delete back | $\Omicron(n)$ — reach the last element |
| access | $\Omicron(n)$ — reach the target element |