Adding to the List

DynamicArray.add puts a new value at the end of the list. Let’s do the same for LinkedList.add. So we are implementing the addLast from the last chapter. Our initial implementation there costs $O(n)$ because it has to follow the links from the head to find the last node. Here we have a tail field that points at the last node, so there is no traversal.

Here is the list we start with:

          ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀─── tail
          └───┘      └───┘      └───┘

We want to add 9 to the end. First we make a node to hold it:

Node<T> newNode = new Node<>(value);

Then we link it after the current tail. The new node’s prev points back at the old tail, and the old tail’s next points forward at the new node:

newNode.prev = tail;
tail.next = newNode;

This is the list after those two lines:

          ┌───┐      ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ 9 │
          └───┘      └───┘      └───┘      └───┘
                                  ▲
                                  │
                                tail   (now out of date)

The new node is linked in, but tail still points at the node with value 7. The last node is now 9, so we move tail forward:

tail = newNode;

And now the add is complete:

          ┌───┐      ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ 9 │ ◀─── tail
          └───┘      └───┘      └───┘      └───┘

Notice that we take ownership of tail here. The static methods of the last chapter cannot update tail, because they do not own it. Here, add is a method of the LinkedList, so it owns tail and can update it.

The empty list

If the list is empty, there is no tail to attach to. tail is null, and tail.next = newNode would throw a NullPointerException. When we add to an empty list, the new node is the only node, so it is both the first and the last node, and both head and tail should point at it:

if (head == null) {  // or tail == null
  head = newNode;
  tail = newNode;
}

Putting it all together, here is the complete add method:

public void add(T value) {
  Node<T> newNode = new Node<>(value);
  if (head == null) {  // the list is empty
    head = newNode;
    tail = newNode;
  } else {
    newNode.prev = tail;
    tail.next = newNode;
    tail = newNode;
  }
  size++;
}

The size++ sits outside the if, because both branches add a node. Forgetting it here would make size() return the wrong value.

Time complexity

add is $O(1)$. It allocates one node, sets a fixed number of references, and increments size. None of that depends on the length of the list, because tail already points at the last node.

Compare that to DynamicArray.add, which is amortized $O(1)$. add in DynamicArray has to check whether the backing array is full and call grow() to allocate a bigger array and copy everything over. The linked list does not have a fixed capacity, so it never has to grow. It just allocates a new node and links it in each time an element is added.