Removing a Given Item

Earlier in this chapter we removed an item by index: we traverse to the predecessor and point its next past the target. What if we are handed the item to remove directly, as a ListItem, instead of an index?

In a forward-only list, this is the same problem we ran into with insertBefore. To unlink item, its predecessor’s next has to skip over it. But from item alone, with only forward links, we cannot reach the predecessor.

But if our item has a prev link, we can reach both of its neighbors directly. item.prev is its predecessor, and item.next is its successor. To remove item, we connect those two neighbors to each other, so that the list skips over item:

item.prev.next = item.next;
item.next.prev = item.prev;

We do have to be careful at the two ends. If item is the first item, it has no predecessor (item.prev is null), so item.prev.next would throw a NullPointerException. And if item is the last item, item.next is null. We guard each side with a null check before updating it:

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 version of remove is $O(1)$: a fixed number of reference changes, no matter how long the list is.

Keep in mind if you call this remove and give it the head of the list, it will unlink that item, but it will not update the outside head reference to point at the new first item. The caller has to do that.