Inserting Before an Item

Let’s write insertBefore, which takes the list, an index, and a value, and inserts a new item holding that value right before the item at the given index.

Here is the list we start with.

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

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

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

The new item goes between the item with value 3 and the item with value 5. The only next reference we need to redirect belongs to the item with value 3, the item before the target. The target itself (value 5) does not change. The new item points to it.

So to insert before the item at index i, the item we have to change is the item at index i - 1, its predecessor. Here is a quick way to implement insertBefore by reusing insertAfter.

public static ListItem insertBefore(ListItem head, int index, int value) {
  if (index == 0) {
    return addFirst(head, value);
  }
  return insertAfter(head, index - 1, value);
}

The index == 0 case is special. There is no item before the first one, so “insert before index 0” means putting the new item at the front. That is a prepend, which is what addFirst does.

insertBefore is $O(n)$ in time because insertAfter is $O(n)$ in time. It is $O(1)$ in auxiliary space, since both addFirst and insertAfter are $O(1)$ in auxiliary space.

insertBefore also has to handle invalid indices, same as the other index-based operations.