Adding Nodes to a Linked List: The Traverse-to-index-1 Pattern
How to insert a node at a given index in a linked list — the traverse-to-index-1 pattern, JavaScript code, a worked walkthrough, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Arrays let you jump to any index in one step. Linked lists do not — a node only knows the address of the next node, so reaching position k means walking k hops from the head. That single constraint shapes every linked-list operation, and insertion is where it bites first.
Insert a node into an array at index k and you shift every element after it — O(n) of copying. Insert a node into a linked list and the physical move is free: you rewire two pointers and the list is done growing. The cost hides somewhere else entirely, in finding the spot. Understanding that trade is the whole point of this problem.
The problem
Given the head of a singly linked list, an integer index, and a value val, insert a new node holding val so it lands at position index (0-based). Return the head of the modified list. If index is 0 the new node becomes the head; if index is past the end of the list, the insertion is skipped.
Input: head = 10 -> 20 -> 30, index = 1, val = 99
Output: 10 -> 99 -> 20 -> 30The new node slots in at index 1, pushing the old node-at-index-1 (20) and everything after it one position to the right. Two boundary cases decide whether your code is correct: inserting at the head (index 0, where there is no predecessor to rewire) and inserting past the tail (where there is no valid spot at all).
The brute force baseline
You could convert the list to an array, splice the value in, and rebuild the list from scratch.
function insertAtIndex(head, index, val) {
const values = [];
for (let node = head; node !== null; node = node.next) {
values.push(node.value);
}
values.splice(index, 0, val); // array insert
// rebuild a fresh linked list
let dummy = new Node(0), tail = dummy;
for (const v of values) {
tail.next = new Node(v);
tail = tail.next;
}
return dummy.next;
}It works, but it throws away the one advantage a linked list has. splice shifts every element after the insertion point, then you allocate a brand-new node for every value in the list — O(n) extra memory and O(n) allocations to change one link. The list was already a chain of pointers; you don't need to melt it down to add one bead.
The key insight: you only need the predecessor
A linked-list insertion is a pointer splice. To wedge a node in at index k, you don't touch the whole list — you only need the node at index k - 1, the predecessor. Once you're standing on it, two assignments finish the job:
newNode.next = predecessor.next // new node points to the old successor
predecessor.next = newNode // predecessor now points to the new nodeThe order is not optional. Set predecessor.next = newNode first and you've overwritten the only reference to the rest of the list — the old successor is now unreachable. Link the new node forward first, then redirect the predecessor. That's the pattern: walk to index - 1, then splice. Head insertion (index 0) is the one case with no predecessor, so it gets a small branch of its own.
The optimal solution
function insertAtIndex(head, index, val) {
const newNode = new Node(val);
if (index === 0) {
newNode.next = head;
return newNode;
}
let curr = head;
for (let i = 0; i < index - 1 && curr !== null; i++) {
curr = curr.next;
}
if (curr !== null) {
newNode.next = curr.next;
curr.next = newNode;
}
return head;
}Three moving parts. The index === 0 branch handles head insertion by pointing the new node at the old head and returning it as the new head — no traversal, no predecessor. Otherwise curr walks forward until it lands on index index - 1; the loop stops early if curr falls off the end (curr !== null in the guard), which is how the "index past the tail" case fails safely. The final if (curr !== null) confirms there really is a predecessor before splicing, and returning the original head reflects that a mid-list insert never changes it.
Walkthrough
Trace insertAtIndex(head, 1, 99) on the list 10 -> 20 -> 30. Since index = 1, the loop condition i < index - 1 is i < 0, so the loop body never runs — curr stays on the head, which is exactly index 0, the predecessor we need.
| Step | Line | curr | Action | List |
|---|---|---|---|---|
| 1 | create | — | newNode = Node(99), floating, unlinked | 10 -> 20 -> 30 |
| 2 | index === 0? | — | 1 is not 0 → traverse | 10 -> 20 -> 30 |
| 3 | curr = head | Node(10) | pointer starts at index 0 | 10 -> 20 -> 30 |
| 4 | loop guard | Node(10) | 0 < 0 is false → skip loop | 10 -> 20 -> 30 |
| 5 | curr !== null? | Node(10) | true → predecessor found | 10 -> 20 -> 30 |
| 6 | newNode.next = curr.next | Node(10) | 99 now points to Node(20) | 10 -> 20 -> 30 |
| 7 | curr.next = newNode | Node(10) | 10 now points to 99 | 10 -> 99 -> 20 -> 30 |
| 8 | return head | — | head is still Node(10) | 10 -> 99 -> 20 -> 30 |
Steps 6 and 7 are the splice, in the order that matters. After step 6, node 99 and node 10 both point to 20 — a harmless temporary fork. Step 7 collapses it by redirecting 10 to 99. Flip those two lines and step 6 would have nothing left to read, because 10.next would already be 99.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Array splice + rebuild | O(n) | O(n) | copies every value and re-allocates the whole list |
| Traverse + splice | O(index) | O(1) | walks at most index - 1 hops, then two pointer writes |
The pointer version does the insertion itself in O(1) — allocate one node, write two links. All the time goes into reaching the predecessor, which is O(index) and at worst O(n) for a tail insert. Space is O(1): one new node, no auxiliary structures. That O(1) rewiring is the linked list's headline advantage over an array, but it only pays off once you're already positioned at the spot.
Common mistakes
- Splicing in the wrong order. Writing
curr.next = newNodebeforenewNode.next = curr.nextorphans the rest of the list. Always link the new node forward first. - Forgetting the head case. When
index === 0there is no predecessor to stand on. Without the early branch,currstays at the head and the node lands at index 1, not 0. - Traversing to
indexinstead ofindex - 1. Land on the node at the insertion point and you'll splice one position too late. You need the node just before it. - No boundary guard. If
indexexceeds the list length,currwalks off the end. Thecurr !== nullconditions in both the loop and the finalifare what stop a null-pointer crash. - Losing the head reference. For any non-head insert, the original
headis still the front of the list — return it, don't returncurrornewNode.
Where this pattern shows up next
The walk-to-a-position-then-rewire idea is the backbone of nearly every linked-list operation:
- Introduction to Linked List — the node/pointer model these insertions build on.
- Design Linked List — bundles insert, delete, and get into one class using this exact traversal.
- Deleting Nodes in Linked List — the mirror image: find the predecessor, then splice a node out.
- Middle of the Linked List — traversal taken further, using two pointers to find a position without counting.
You can also step through the insertion interactively to watch the new node float in and the two pointers rewire, one line at a time.
FAQ
Why is inserting into a linked list O(1) but inserting into an array O(n)?
The physical insertion differs. An array stores elements in contiguous memory, so making room at index k forces every later element to shift one slot right — O(n) copies. A linked list stores nodes anywhere in memory connected by pointers, so inserting means changing two pointers and nothing moves — O(1). The catch is that reaching index k in a linked list is itself O(k), because you can only get there by walking from the head, whereas an array indexes in O(1).
Why do you traverse to index minus one instead of index?
Because splicing a node in requires editing the .next pointer of the node before the insertion point. That predecessor is the only node whose link needs to change — it must stop pointing at the old successor and start pointing at the new node. If you stopped on the node at index itself, you'd have no handle on the node before it, and a singly linked list gives you no way to walk backward.
Does the order of the two pointer assignments matter?
Yes, critically. You must set newNode.next = curr.next before curr.next = newNode. The new node needs to grab the old successor while curr.next still points to it. If you redirect curr.next to the new node first, you overwrite the only reference to the rest of the list and lose everything after the insertion point. Link forward, then redirect.
What happens if the index is larger than the list length?
The insertion is skipped and the list is returned unchanged. As curr traverses, the loop condition curr !== null stops it the moment it runs out of nodes, leaving curr as null. The final if (curr !== null) then guards the splice, so no pointer is written and no crash occurs. This is a deliberate boundary guard — an out-of-range index has no valid position to occupy.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.