Exercise IX

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$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