Keeping the Size

The first operation we write is size.

In the last chapter, size had to traverse the whole list and count the nodes. That made it $O(n)$.

Our LinkedList keeps a size field, so the operation just reads it:

public int size() {
  return size;
}

This is $O(1)$ no matter how long the list is, the same as DynamicArray.size().

As with DynamicArray, we have to maintain the invariant that size always equals the actual number of nodes. Every operation that adds a node must do size++, and every operation that removes one must do size--. If one of them does not update size, size() returns a wrong answer.