Linked List Foundations
8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.
What is a Linked List?
A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory. The list starts at HEAD and ends at null.
The intuition
Think of a treasure hunt. Each clue tells you where to find the next clue. You cannot jump directly to clue #5 without following clues 1 -> 2 -> 3 -> 4 first.
- Linked list = VALUE + POINTER per node
- Entry point is HEAD
- Last node points to null
- Sequential access (no O(1) index lookup)
- Great for frequent insert/delete operations
When to use it
- When insert/delete in the middle happens often
- When you do not need random index access
- When data size changes frequently
A real-world analogy
A train where each coach is linked to the next coach. To reach coach 7, you walk through coaches 1 to 6.
Node Anatomy: Value + Next
A node has two core parts: the stored data (value) and a pointer (next) to another node. In singly linked lists, each node only knows its next node.
The intuition
Each node is like a sticky note containing (1) information and (2) directions to the next sticky note.
- Node = { value, next }
- next can store another node reference or null
- A broken pointer breaks traversal
- Always save next before rewiring in tricky operations
When to use it
- When learning pointer manipulation
- Before implementing reverse/merge/delete
- To debug pointer bugs visually
A real-world analogy
A note saying: 'My value is 42. To continue, go to room B-12.'
Traversal: How We Visit Nodes
Traversal means moving from head to null using a current pointer. This is the backbone of almost every linked list algorithm.
The intuition
You walk one stepping stone at a time across a river. Missing one step means you lose the path.
- Initialize current = head
- Process current node
- Move current = current.next
- Stop when current becomes null
Time complexity
| Best | O(1) for empty list |
|---|---|
| Average | O(n) |
| Worst | O(n) |
Space complexity: O(1)
When to use it
- Finding length
- Searching a value
- Printing or transforming all nodes
A real-world analogy
Like reading a chain of emails where each email links to the next one.
curr = head
while curr is not null:
process(curr.value)
curr = curr.nextInsert by Rewiring Pointers
To insert a node into a linked list, traverse from head to find the target position, create the new node, point its next to the current next, then rewire the previous node's next to the new node. Two pointer reassignments: that's it.
The intuition
Imagine a chain of paper clips. To add one in the middle, unhook the connection at that spot, clip the new one in, and re-link. No need to shift everything.
- Traverse from head to find insert position
- Create newNode with the value to insert
- newNode.next = curr.next (link new to rest)
- curr.next = newNode (splice new into chain)
- Order matters: link forward first, then rewire back
Time complexity
| Best | O(1) if position is known |
|---|---|
| Average | O(n) to find position |
| Worst | O(n) |
Space complexity: O(1)
When to use it
- Adding elements in the middle of a list
- Building sorted lists by insertion
- Queue/stack push operations
A real-world analogy
Adding a new train car between two existing cars. Just change the couplings, no need to move any other cars.
Delete by Rewiring Pointers
To delete a node, traverse from head to find the node just before the target. Then bypass the target by pointing prev.next directly to target.next. The target node is effectively removed from the chain.
The intuition
Like removing a link from a chain: reconnect the two neighbors and the removed link falls away.
- Traverse from head to find the node before the target
- Save target reference: target = curr.next
- Bypass: curr.next = target.next
- Target node is now unreachable and removed
- Head deletion needs special handling or a dummy node
Time complexity
| Best | O(1) if prev is known |
|---|---|
| Average | O(n) to find position |
| Worst | O(n) |
Space complexity: O(1)
When to use it
- Removing elements from the middle of a list
- Problems like remove nth node from end
- Dequeue / stack pop operations
A real-world analogy
Removing a broken link from a chain by connecting its two neighbors directly.
Reverse Pattern: prev, curr, next
Reversing a linked list means making every node point backward instead of forward. The tricky part: when you flip node B's pointer from C back to A, you lose access to C forever, because B was your only way to reach C! The solution is three pointers working together: prev (the node we just reversed), curr (the node we're about to flip), and next (a 'bookmark' saving where to go after we flip curr). Before flipping B→A, we first save C in 'next'. Then we safely flip B→A. Then we slide all three pointers one step forward and repeat.
The intuition
Imagine a line of people holding hands: A—B—C. You want them to face the opposite direction. Before person B lets go of C's hand to grab A's hand, someone must remember where C is standing, otherwise C is lost. That 'someone' is the next pointer. It bookmarks C so that after B turns around (grabs A), we can walk to C and repeat the process.
- The core problem: flipping a pointer destroys the forward link to the rest of the list
- 'next' acts as a bookmark: it saves curr.next BEFORE we break the link
- Each iteration does exactly 4 things: (1) Save next, (2) Flip curr→prev, (3) Advance prev, (4) Advance curr
- prev starts at null because the first node's 'next' should become null (end of reversed list)
- After the loop, curr is null (past the end) and prev points to the old tail, which is the new head
- Always save next FIRST. If you flip before saving, you lose the rest of the list forever
- This pattern appears in: reverse linked list, palindrome check, reorder list
Time complexity
| Best | O(1) for empty/single node |
|---|---|
| Average | O(n) |
| Worst | O(n) |
Space complexity: O(1)
When to use it
- Reverse linked list
- Palindrome linked list
- Reorder list second-half reversal
A real-world analogy
Reversing a conga line: each person must first tap the person ahead of them (save next), then turn around to face the person behind (flip pointer), before the next person can do the same. If anyone turns around without tapping first, the line ahead is lost.
prev = null // nothing before head yet
curr = head // start at the first node
while curr is not null: // visit every node once
next = curr.next // SAVE bookmark before we break the link!
curr.next = prev // FLIP: point backward instead of forward
prev = curr // ADVANCE prev one step forward
curr = next // ADVANCE curr using our saved bookmark
return prev // prev is the new head (old tail)Two Pointers: Slow & Fast
Two pointers moving at different speeds unlock elegant O(n) linked list solutions. Slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.
The intuition
Imagine two runners on a track. If one runs twice as fast, by the time the fast runner finishes, the slow runner is exactly at the halfway mark.
- Middle of list: when fast reaches the end, slow is at the middle
- Useful for splitting a list into two halves
- Always check fast and fast.next before two-step move
- Avoids the need to count length first then traverse again
Time complexity
| Best | O(1) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
Space complexity: O(1)
When to use it
- Find middle node
- Palindrome linked list (find middle, reverse second half)
- Reorder list
A real-world analogy
Two people walking along the same path, one takes double-sized steps. When the fast walker reaches the end, the slow walker is at the midpoint.
Linked List Pattern Playbook
Most linked list problems are combinations of a few reusable patterns: traversal, rewiring, reverse, two pointers, and dummy node.
The intuition
Treat linked list solving like assembling LEGO blocks—small reliable blocks combine into larger solutions.
- Pattern > memorizing full solutions
- Track pointers explicitly on paper
- Protect next pointer before rewiring
- Use two pointers for middle-finding and distance-based tasks
When to use it
- Interview preparation
- Debugging pointer-heavy code
- Designing optimal linked-list solutions quickly
A real-world analogy
A chef's knife skills—once fundamentals are strong, many dishes become easier.