Inserting After an Item

addFirst and addLast add to the two ends of the list. But often we want to add an item somewhere in the middle. Let’s write insertAfter, which takes the list, an index, and a value, and inserts a new item holding that value right after the item at the given index.

Here is the list we start with. Say we want to insert 9 after the item at index 1 (the item with value 5):

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

The first step is to traverse to the item at the index. This is the same traversal used in get and set. Take index steps from the head:

ListItem current = head;
for (int i = 0; i < index; i++) {
  current = current.next;
}

At the end of the loop, current points to the item at the given index:

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

Now we want the new item to go between the item current points to and the item after it. Let’s create the new item first.

ListItem newItem = new ListItem(value);

Now point its next at the item that currently comes after current:

newItem.next = current.next;

This schematic shows the current state:

                   current
                      │
                      ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘
                                ▲
                    ┌───┐       │
        newItem ──▶ │ 9 │ ──────┘
                    └───┘

Notice that the item with value 5 still points at 7, and now the new item also points at 7. We need to get the item with value 5 to point at the new item instead. We do that by changing current.next to point at newItem:

current.next = newItem;

Here is how the list looks after that change:

                   current
                      │
                      ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │     │ 7 │ ──▶ null
          └───┘     └───┘     └───┘
                      │         ▲
                      ▼         │
                    ┌───┐       │
        newItem ──▶ │ 9 │ ──────┘
                    └───┘

which is effectively the same as:

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

Putting it together (and assuming a valid index, as before):

public static ListItem insertAfter(ListItem head, int index, int value) {
  ListItem current = head;
  for (int i = 0; i < index; i++) {
    current = current.next;
  }
  ListItem newItem = new ListItem(value);
  newItem.next = current.next;
  current.next = newItem;
  return head;
}

We return the head, but notice it never actually changes here. Unlike addFirst, inserting after an existing item never changes which item comes first. We return it only to keep the same shape as our other operations.

insertAfter is $O(n)$ in time. The splice itself (creating the item and rewiring two references) is $O(1)$. The cost is the traversal to reach the index.

Inserting into an array is also $O(n)$, but for a different reason. There is no traversal, since we can jump straight to the index. But to open up a gap, every element after that position has to shift one slot to the right.

insertAfter is $O(1)$ in auxiliary space, since it allocates only one new item and uses a constant number of references for the traversal.

Like the other index-based operations, insertAfter must handle invalid indices.