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.

• 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

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.

• Node = { value, next }
• next can store another node reference or null
• A broken pointer breaks traversal
• Always save next before rewiring in tricky operations

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.

• Initialize current = head
• Process current node
• Move current = current.next
• Stop when current becomes null

curr = head
while curr is not null:
    process(curr.value)
    curr = curr.next

Insert 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.

• 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

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.

• 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

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 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

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.

• 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

Linked List Pattern Playbook

Most linked list problems are combinations of a few reusable patterns: traversal, rewiring, reverse, two pointers, and dummy node.

• Pattern > memorizing full solutions
• Track pointers explicitly on paper
• Protect next pointer before rewiring
• Use two pointers for middle-finding and distance-based tasks

All DSA learning paths