Adding in Order

add is the operation that does the most work, because it must place the new value in the position that keeps the list sorted. Unlike a plain LinkedList, it cannot simply append to the end.

The plan is: traverse from the first real node until we reach the first value that is greater than the new one, then splice the new node in just before it. The splice itself is the same reference manipulation we used in the previous chapter, so we will put it in a small private helper:

private Node<T> insertBetween(T value, Node<T> before, Node<T> after) {
  Node<T> node = new Node<>(value);
  node.prev = before;
  node.next = after;
  before.next = node;
  after.prev = node;
  size++;
  return node;
}

With that helper, add traverses to find the insertion point and splices:

public void add(T value) {
  if (value == null) {
    throw new NullPointerException();
  }
  Node<T> current = head.next;
  while (current != tail && current.value.compareTo(value) <= 0) {
    current = current.next;
  }
  insertBetween(value, current.prev, current);
}

The null check at the top enforces the SortedList contract we wrote earlier: a value has to be non-null so that compareTo can order it.

The loop stops when current is the back sentinel, or when current.value is greater than the new value. The new value belongs before current, so we insert between current.prev and current.

Notice there is no special branch for inserting at the front, at the back, or into an empty list. All three are handled by the same code because of the sentinels.