Removing an Item

We have several ways to add an item. Let’s write remove, which takes the list and an index, and removes the item at that index.

Here is the list we start with.

          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘
index:      0         1         2

Say we want to remove the item at index 1 (the item with value 5), so that the result is:

          ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘
index:      0         1

Removing an item means rerouting one reference. Initially, the item with value 3 points to the item with value 5, and the item with value 5 points to the item with value 7. To drop the item with value 5, we make the item with value 3 point directly to the item with value 7, skipping over the item with value 5.

Just like inserting before, the reference we have to change belongs to the predecessor of the target, the item at the index before it. So we traverse to the predecessor:

        previous
            │
            ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘
index:      0         1         2

The item to remove is previous.next, and the item to skip to is the one after it, previous.next.next. So we reroute the predecessor’s next to point there:

previous.next = previous.next.next;

Here is the list after that rerouting:

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

The item with value 5 is still in memory, and it still points to 7, but nothing in our list points to it anymore. It has been unlinked, and Java’s garbage collector will eventually reclaim it.

If we redraw the list without the removed item, we get:

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

The traversal to the predecessor does not work for the first item, at index 0. The first item has no predecessor, so there is no next reference before it to reroute. Instead, removing the head means the second item becomes the new first item. We just move the head forward:

head = head.next;

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

The old first item (value 3) is now unreferenced, and it will be garbage collected. The new head is the item with value 5, and the list is now:

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

Like addFirst and insertBefore, removing at index 0 changes the head, so remove returns the head:

public static ListItem remove(ListItem head, int index) {
  if (index == 0) {
    return head.next;
  }
  ListItem previous = head;
  for (int i = 0; i < index - 1; i++) {
    previous = previous.next;
  }
  previous.next = previous.next.next;
  return head;
}

remove is $O(n)$ in time because we have to traverse to the predecessor. It is $O(1)$ in auxiliary space since it allocates a constant number of references and variables for the traversal.

Note that removing from an array is also $O(n)$, but for a different reason. There is no traversal. We can jump to the target index. But then we must shift all elements after the target index to the left. That shifting is the $O(n)$ cost.

And remove has the same invalid-index problem as the other operations that take one.