3. Linked Lists

In this chapter, we continue to study implementations of the List interface, this time using pointer-based data structures rather than arrays. The structures in this chapter are made up of nodes that contain the list items. Using references (pointers), the nodes are linked together into a sequence. We first study singly-linked lists, which can implement Stack and (FIFO) Queue operations in constant time per operation and then move on to doubly-linked lists, which can implement Deque operations in constant time.

Linked lists have advantages and disadvantages when compared to array-based implementations of the List interface. The primary disadvantage is that we lose the ability to access any element using $\ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$ or $\ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ in constant time. Instead, we have to walk through the list, one element at a time, until we reach the $\ensuremath{\ensuremath{\mathit{i}}}$th element. The primary advantage is that they are more dynamic: Given a reference to any list node $\ensuremath{\ensuremath{\mathit{u}}}$, we can delete $\ensuremath{\ensuremath{\mathit{u}}}$ or insert a node adjacent to $\ensuremath{\ensuremath{\mathit{u}}}$ in constant time. This is true no matter where $\ensuremath{\ensuremath{\mathit{u}}}$ is in the list.