A Backward Link

Can we make insertBefore as cheap as insertAfter?

public static void insertBefore(ListItem item, int value) {
  ListItem newItem = new ListItem(value);
  newItem.next = item;
  // now we need: predecessor.next = newItem
  // but from `item`, following only forward links, we cannot reach its predecessor
}

From item alone, there is no way to reach the item that points at it. The only thing we can do is start at the head and traverse the list looking for the item whose next is item, and in the worst case that visits every item, so it is .

This comes from how we defined ListItem. Each item holds a reference to the item after it. So from an item we can move forward.

To make insertBefore as easy as insertAfter, we need a way to get from an item to its predecessor. We give each item a second link, a “previous” reference (usually abbreviated prev) pointing to the item before it:

public class ListItem {
  public int value;
  public ListItem next;
  public ListItem prev;  // a link to the item before this one

  public ListItem(int value) {
    this.value = value;
  }
}

Now the list is connected in both directions: each item points forward to the next and backward to the previous. A list whose items link both ways like this is called a doubly linked list.

Here is a schematic of a doubly linked list:

          ┌──────────────┐    ┌──────────────┐    ┌──────────────┐
 head ■─▶ │ ListItem     │    │ ListItem     │    │ ListItem     │
          │   value = 3  │    │   value = 5  │    │   value = 7  │
          │   next ■─────┼──▶ │   next ■─────┼──▶ │   next ■─────┼──▶ null
 null ◀───┼───■ prev     │ ◀──┼───■ prev     │ ◀──┼───■ prev     │
          └──────────────┘    └──────────────┘    └──────────────┘

Here is a more compact way to draw the same thing:

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

With a prev link, inserting before an item no longer requires searching for the predecessor. The predecessor is just item.prev:

public static void insertBefore(ListItem item, int value) {
  ListItem newItem = new ListItem(value);
  newItem.next = item;
  newItem.prev = item.prev;
  item.prev.next = newItem;
  item.prev = newItem;
}

(We are setting aside the case where item is the first item and has no predecessor for now.) This is : four reference assignments and one new item, and none of that depends on the length of the list. Inserting before an item is now as cheap as inserting after one.

The forward-only insertAfter sets two references. This insertBefore sets four. The new item has to be linked in both directions, so it needs a next and a prev, and the two items on either side of it each have to be re-pointed at it, one going forward and one going backward.

This applies to more than insertBefore. Once items carry a prev link, every operation that changes the shape of the list has to keep both links correct. That is every prepend, append, insert, and remove. Each of these operations now has to update twice as many references.

So the second link is a trade. It makes “before” operations as cheap as “after” operations, and it lets us traverse the list in either direction. It also makes every structural change longer and easier to get wrong. Whether the trade is worth it depends on what the list is used for.

The case of the first item

There is still a case insertBefore does not handle. It assumes item has a predecessor, and that assumption is false when item is the first item in the list. Its prev is null, so the line item.prev.next = newItem throws a NullPointerException. There is no predecessor to re-point.

This case is really a prepend: the new item goes in front of everything and becomes the new first item. We wire it up as the new front and leave its prev as null:

newItem.next = item;
newItem.prev = null;
item.prev = newItem;
// and the head must now refer to newItem

So, like addFirst and insertBefore by index, inserting before the first item changes the head. Whoever owns the head reference has to be updated to point at the new first item.