Walking to a Predecessor Node for Index-Based Insert and Remove

Try This First

You have a linked list of five integers: 10 -> 20 -> 30 -> 40 -> 50, with head pointing at 10. You want to insert 99 at index 2, so the result will be 10 -> 20 -> 99 -> 30 -> 40 -> 50.

Before you write any code: which node do you need a reference to in order to do the insertion? What is its data value?

What You Need To Walk In With

• Inserting or removing at an arbitrary index requires a reference to the node one position before the target index, not the target itself.
• The predecessor walk uses the loop for (int j = 0; j < i - 1; j++) prev = prev.next; which runs exactly i - 1 steps, leaving prev at index i - 1.
• After the walk, insertion is prev.next = new Node<>(x, prev.next); and removal is prev.next = prev.next.next;.
• Index 0 is a special case: there is no predecessor node (nothing comes before head), so you must handle it separately with an addFirst-style operation.
• The cost of reaching the predecessor is O(i), because the loop takes i - 1 steps.

How It Works

This list has no dummy head: it holds a head reference (initially null) and a size field only. To work at an arbitrary index i, you cannot jump there directly. You must start at head and follow next links until you reach the node at position i - 1.

The Walk Loop

Node<T> prev = head;
for (int j = 0; j < i - 1; j++) {
    prev = prev.next;
}
// After the loop, prev sits at index i - 1 (the predecessor of i).

The bound j < i - 1 is the key detail. If i is 3, the loop runs twice (j = 0, then j = 1), ending with prev at index 2, which is index 3 - 1.

Insert at Index i (i >= 1)

public void add(int i, T x) {
    if (i == 0) {
        head = new Node<>(x, head);   // no predecessor exists
        size++;
        return;
    }
    Node<T> prev = head;
    for (int j = 0; j < i - 1; j++) prev = prev.next;
    prev.next = new Node<>(x, prev.next);
    size++;
}

The single line prev.next = new Node<>(x, prev.next) does two things at once: it points the new node at the old node at index i (via prev.next on the right side), and it points the predecessor at the new node (via prev.next on the left side). Order matters because the right-hand side is evaluated first.

Remove at Index i (i >= 1)

public T remove(int i) {
    if (i == 0) {
        T val = head.data;
        head = head.next;             // no predecessor exists
        size--;
        return val;
    }
    Node<T> prev = head;
    for (int j = 0; j < i - 1; j++) prev = prev.next;
    T val = prev.next.data;
    prev.next = prev.next.next;       // skip the removed node
    size--;
    return val;
}

The pointer sketch below shows the state just before and after removal at index 2 in a four-node list:

Before:
  head -> [A] -> [B] -> [C] -> [D] -> null
                  ^
                 prev (index 1, predecessor of index 2)

After:
  head -> [A] -> [B] ---------> [D] -> null
                  ^
                 prev.next now skips [C]

Worked Example: Predict, Then Check

Consider this list: “alpha” -> “beta” -> “gamma” -> “delta”, size = 4. You call remove(2).

Trace the walk loop and the pointer update. What value is returned, and what does the list look like afterward?

A Common Mistake

A common error is writing the loop bound as j < i instead of j < i - 1. That walks one step too far, landing prev at the target node (index i) instead of its predecessor. With prev pointing at the wrong node, prev.next = new Node<>(x, prev.next) inserts after position i rather than before it, and remove skips the wrong node entirely. The fix is to remember that you need to stop one step early, so the bound must be j < i - 1. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The walk takes O(i) time because you follow i - 1 links. That means inserting or removing near the end of a long list is expensive: every call re-traverses from head. This is the main structural trade-off compared to an array, where index-based access is O(1). If your workload involves frequent inserts and removes at the end, consider maintaining a tail reference to skip the walk for the last position.

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.