Boundary Cases: Insert at Front or Back

Try This First

You have a list [a, b, c] (size 3). You call add(0, "z"). Without looking at any code, describe what the list looks like after the call and identify which simpler operation handles it.

What You Need To Walk In With

• add(int i, T x) inserts x so that it ends up at index i.
• When i == 0, the insert is at the front: head must change, so this is exactly what addFirst does.
• When i == size, the insert is at the end: this is exactly what append (add-to-end) does.
• These two boundary cases must be detected and routed before the walk-to-predecessor logic runs, because the walk assumes a predecessor exists and will throw a NullPointerException when i == 0.
• Delegating to addFirst and append keeps the code clean and avoids duplicating pointer-update logic.

How It Works

The add(int i, T x) method has three regions:

1. Boundary at the front (i == 0): delegate to addFirst.
2. Boundary at the back (i == size): delegate to append.
3. Middle (0 < i < size): walk to the predecessor at index i - 1, then splice in the new node.

public void add(int i, T x) {
    if (i < 0 || i > size) throw new IndexOutOfBoundsException();

    if (i == 0) {
        addFirst(x);          // updates head; no walk
        return;
    }
    if (i == size) {
        append(x);            // walks to tail (or uses tail ref); no special head logic
        return;
    }

    // Middle case: walk to predecessor
    Node<T> current = head;
    for (int j = 1; j < i; j++) {   // walk i-1 times: stop at index i-1
        current = current.next;
    }
    Node<T> newNode = new Node<>(x);
    newNode.next = current.next;      // point new node forward
    current.next = newNode;           // predecessor points to new node
    size++;
}

A pointer sketch for inserting "m" at index 2 in [a, b, c]:

Before:  head -> [a] -> [b] -> [c] -> null
                         ^
                    current (index 1, the predecessor)

After:   head -> [a] -> [b] -> [m] -> [c] -> null
                         |      ^      |
                  current.next  new   old current.next

The key detail: newNode.next is set before current.next is updated. Reversing those two lines loses the reference to [c].

Worked Example: Predict, Then Check

You have list = [a, b, c] (size 3). You call list.add(3, "d"). Which branch of the method runs, and what does the list look like after?

A Common Mistake

A common error is skipping the i == 0 boundary check and letting the walk-to-predecessor logic run for every index. When i == 0, there is no predecessor: current starts at head, and the for-loop body (current = current.next) runs zero times, so current is head. Setting current.next = newNode makes the old head the second node, which is correct for the pointer chain, but head itself still points to the old first node. The new node is now at index 1, not index 0, and head is wrong. The fix is to check i == 0 first and call addFirst, which correctly updates head. (Source: S20.Lab5-LL_NDH)

Go Deeper (optional)

Both boundary delegations run in O(1) time if the list maintains a tail reference (as the dummy-head-and-tail variant does). In the no-dummy-head form covered here, append still walks to the tail in O(n). The middle case is O(n) because of the predecessor walk. Understanding which branch runs tells you the cost of any given add(i, x) call before you profile it.

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.