Singly and Doubly Linked Lists

A ListItem with only a next reference gives us a singly linked list: each item points forward, and we can traverse it in one direction only. A ListItem with both next and prev gives us a doubly linked list: each item points forward and backward, and we can traverse it in either direction.

The two trade off against each other. A singly linked list is simpler and uses less memory per item, but anything that needs an item’s predecessor costs $O(n)$. A doubly linked list makes the predecessor available directly, at the cost of keeping two references correct on every structural change.

There is one problem we ran into several times, and it is the same in both designs. The head, and a tail if we tried to keep one, were variables in the caller’s code, outside the operations. Any operation that changed which item was first, like addFirst or removing the first item, could unlink the items correctly but could not update the head, because the head belonged to the caller. We worked around it by returning the new head and asking the caller to store it back. That works only as long as the caller does that every time.

The fix is to put the head and the tail inside an object, together with the operations that change them, so that no code outside has to update them. That object is the LinkedList abstraction, and we build it in the next chapter.