A Class to Own the List

Here is the LinkedList class that owns the list’s head, tail, and size:

public class LinkedList {
  private ListItem head;
  private ListItem tail;
  private int size;

  public LinkedList() {
    head = null;
    tail = null;
    size = 0;
  }
}

A fresh LinkedList is empty, so there is no first item and no last item: head and tail are both null, and size is 0.

All three fields are private. Code outside the class cannot set head to some arbitrary item. The only way the list changes is through the methods we write, and those methods are responsible for keeping the invariant.

Where to Put ListItem

The list is still made of ListItem objects internally. The question is where the ListItem class should live. In the last chapter it was a top-level class with public fields that any client could read and write.

But who actually needs ListItem? A user of our list adds items, gets them by index, and removes them. The ListItem class that wraps each item is only a detail of how the list is implemented, so we should keep it private. Specifically, we do not want a client to be able to update the next link of a ListItem and break the list.

So we nest ListItem inside LinkedList and mark it private:

public class LinkedList {
  private ListItem head;
  private ListItem tail;
  private int size;

  private static class ListItem {
    int value;
    ListItem next;
  }

  public LinkedList() {
    head = null;
    tail = null;
    size = 0;
  }
}

Now ListItem is part of the internal implementation of LinkedList. Code outside the class cannot name the type, create one, or read its fields.

The nested class is marked static too. It means that a ListItem does not belong to a particular LinkedList object. A ListItem does not have a this reference to a LinkedList, and it cannot access the fields of any LinkedList.

The nested class is not finished. Its value is an int, so the list can only hold ints. And it has only a next link, so we cannot step backward. We fix both in the next section.