Inserting at a Specific Position
What you'll learn: How to add a new node at any position in a linked list by carefully navigating and adjusting pointers.
The Core Idea
Imagine you have a chain of paper clips, and you want to insert a new red clip exactly at position 3. You can't just drop it in—you need to:
- Walk along the chain until you reach position 2 (one before where you want to insert)
- Unhook the connection between position 2 and position 3
- Hook your new red clip to position 3
- Hook position 2 to your new red clip
In a linked list, inserting at position k works the same way. You traverse the list to find the node at position k-1, then adjust two pointers to "weave in" the new node.
The Process
Step 1: Traverse to position k-1
Start at the head and move forward k-1 times. This node will be your "anchor"—the node just before your insertion point.
Step 2: Create the new node
Allocate memory for a new node and set its data.
Step 3: Wire up the pointers carefully
- Set the new node's
nextpointer to point to what the anchor currently points to - Update the anchor's
nextpointer to point to the new node
Order matters! If you change the anchor's pointer first, you lose track of the rest of the list.
Edge Cases
- Inserting at position 0? Use your head-insertion logic instead.
- Position beyond list length? Check bounds or handle gracefully (some implementations insert at the tail).
Key Takeaway: Inserting at position k requires traversing to node k-1 and carefully rewiring two pointers: first the new node's next, then the previous node's next.