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 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.