Singly vs. Doubly Linked Lists

A doubly linked list adds a backward reference to each item:

public class ListItem {
  public int value;
  public ListItem next;
  public ListItem prev;

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

Solution

In a singly linked list, each item has only a next reference, so the list can only be traversed forward. In a doubly linked list, each item also has a prev reference to the item before it, so the list can be traversed in either direction, and you can reach any item’s predecessor directly, without a traversal.

Solution

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;
}

Solution

public static void remove(ListItem item) {
  if (item.prev != null) {
    item.prev.next = item.next;
  }
  if (item.next != null) {
    item.next.prev = item.prev;
  }
}

This updates the neighboring items’ links, but it cannot update the caller’s head. If item is the first item, the caller must also set head = item.next. If it is the only item, item.next is null, so that assignment makes the list empty.

Solution

With prev, you can reach an item’s predecessor in one step, so insertBefore and removing a given item both drop from $O (n)$ to $O (1)$ . You can also traverse the list in either direction. The cost is that any operation that inserts or removes an item now has to update both the next link and the prev link instead of one. Each item also uses memory for an extra reference. And the next and prev links can end up inconsistent if either update is missed.