3. Linked Lists

In this chapter, we continue to study implementations of the $ \mathtt{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. The nodes are linked together into a sequence using references (pointers). We first study singly-linked lists, which can implement $ \mathtt{Stack}$ and (FIFO) $ \mathtt{Queue}$ operations in constant time per operation.

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



Subsections
opendatastructures.org