List ADT: Efficient Implementation

We want to implement the List ADT so that all core operations are in $O(1)$. We claim this can only be done using a doubly linked list (with a TAIL pointer).

Exercise Give an example operation of the List ADT which cannot be implemented in constant time using an array-based or singly linked list implementation.

Solution

The insertBefore operation will be at the best linear time:

  • In an array-based implementation, we need to shift all the elements at the given position to the right to make room for the given value to be inserted before the given position.

  • In a singly linked list, we need to traverse the list from the HEAD node to reach the node (position) before the given position. We must do this search because there is no "previous" pointer to get hold of a node before a given position quickly.