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 as an example one 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 best linear time:

  • In an array-based implementation, we need to shift all the elements at the given position to 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 quickly get hold of a node before a given position.