Why the List Needs an Abstraction

In the last chapter, every operation that changed the shape of the list (addFirst, addLast, remove) could change the head of the list. So each one returned the new head, and the caller had to assign it to its own head variable. If the caller forgot, the change was lost. The same was true of tail.

A similar issue arose with size. A linked list represented by a head reference does not record how many items it holds. If you need that information, you have to count the items, or maintain a separate size variable. If you maintain it, every time you call an operation that adds or removes an item, you have to remember to update size. If you forget, the size variable is wrong.

These three things, head, tail, and size, are facts about the list as a whole. They have to agree with each other and with the items: head points at the first item, tail points at the last, and size equals the number of items. These are the invariants of the list. The problem in the last chapter was that no one owned the invariants.

More importantly, a client who wanted to use the list had to know about the ListItem objects and how to manipulate them. But that is how the list is built, not what it does. A client who only wants to add, get, and remove items should not have to know how the item is stored and linked together, just as a client of DynamicArray does not have to know there is an array inside.

So we want one object that does two things:

• It owns head, tail, and size and keeps them consistent on every operation, so the invariant holds.
• It hides the ListItem objects and the links, exposing only the operations a user of a list needs.

The first is encapsulation, and the second is information hiding, the same two ideas behind DynamicArray.