From ListItem to Node

We have a LinkedList class that owns its head, tail, and size, with a private nested ListItem. Before writing the operations, we make three changes to that nested class.

A better name

The standard name for one element of a linked structure is a node. We will use nodes again in trees and graphs, where “item” would not fit as well. So let’s use the standard name and call the class Node.

A backward link

At the end of the last chapter, we added a prev link: a reference from each item back to the one before it. This makes it easy to traverse the list in both directions. We named a list whose nodes link both ways a doubly linked list.

So we build LinkedList as a doubly linked list: every Node carries both a next and a prev. The first node’s prev is null and the last node’s next is null.

A generic value

DynamicArray and SortedArray are generic. Let’s do the same here. The node stores a value of type T, and the list becomes LinkedList<T>.

Putting it together

Putting the three changes together:

public class LinkedList<T> {
  private Node<T> head;
  private Node<T> tail;
  private int size;

  private static class Node<T> {
    T value;
    Node<T> next;
    Node<T> prev;

    Node(T value) {
      this.value = value;
    }
  }

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

The nested Node<T> declares a T of its own. That is not a typo, and it is not the same T as the one on LinkedList<T>. A static nested class belongs to the class, not to any instance of it, so it cannot use the outer class’s type parameter. It has to declare its own.

That sounds like the two type parameters could end up as different types, but they do not, because the list is the only code that ever creates a node. When a LinkedList<String> writes new Node<>(value), the field it stores the node in is declared Node<T>, so Java fills in String for the node’s T as well. The two Ts end up being the same type in every node the list makes.

The Node constructor takes a value and stores it. The next and prev links are null by default, which is what we want when we create a new node that is not yet in the list.

The operations

We also have to decide what the class offers. The last chapter gave us a long list of methods: addFirst, addLast, insertAfter, insertBefore, remove, and the rest. We are not going to reimplement all of them.

We make our LinkedList offer the same operations as DynamicArray. This also fits well into my plan for the next chapter where we extract the common operations into a List interface and implement it with both DynamicArray and LinkedList. The two classes will have the same public operations, but different performance characteristics.

So LinkedList gets the same public operations as DynamicArray:

• add(value) — add a value to the end of the list
• get(index) — return the value at an index
• set(index, value) — replace the value at an index
• size() — return the number of values in the list
• indexOf(value) and contains(value) — find a value
• remove(index) — remove the value at an index
• remove(value) — remove the first occurrence of a value

We will implement them one by one in the next several sections of this chapter.