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. The nodes are linked together into a sequence using references (pointers). We first study singly-linked lists, which can implement Stack and (FIFO) Queue operations in constant time per operation.
Linked lists have advantages and disadvantages relative to array-based implementations of the List interface. The primary disadvantage is that we lose the ability to access any element using or in constant time. Instead, we have to walk through the list, one element at a time, until we reach the th element. The primary advantage is that they are more dynamic: Given a reference to any list node , we can delete or insert a node adjacent to in constant time. This is true no matter where is in the list.