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.

OperationAsymptotic runtime
insert front
insert middle
insert back
delete front
delete middle
delete back
access
Solution
OperationAsymptotic runtime
insert front$\Omicron(1)$ — point the head to a new node
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