Linked Lists
Nodes joined by pointers: how singly and doubly linked lists work, plus the reverse, dummy-node and fast/slow pointer patterns.
beginner40 min#linked-list#pointers#two-pointers#cycle-detection
Prerequisites: Arrays and Dynamic Arrays, Memory, References, and Pointers
Why it matters
Linked lists are the simplest structure built from nodes and references, so they are the training ground for pointer thinking. The same skills carry over to trees, graphs, hash-table chains and LRU caches. They are also a favorite interview topic: reversing a list, finding a cycle, or merging two lists tests whether you can manipulate references without losing the rest of the structure.
Intuition
An array is a row of lockers; a linked list is a scavenger hunt. Each clue (a node) holds a value and a note saying where the next clue is. You only ever hold the first clue, called the head, and you must follow notes one at a time to reach anything else. In exchange, adding a clue in the middle is easy: write a new note and change one old note to point at it. Nothing has to slide over.
head
|
v
[1|*]--->[2|*]--->[3|*]--->[4|/] "/" means next is null / None
Here is the same idea as a picture, first singly linked and then doubly linked.
A doubly linked list adds a second note, prev, pointing backwards. That lets you delete a node when you hold only that node (you can reach both neighbors) and walk in either direction, at the cost of one extra reference per node and more links to keep consistent.
How it works
- Node: an object with a value and a
nextreference. The last node'snextis null. - Access by position requires walking from the head, so
get(i)is O(i). - Insert or delete after a known node rewires one or two references, so it is O(1) once you are standing there. Finding the spot is what costs O(n).
- Tail pointer: keep a reference to the last node and appending becomes O(1) too.
- Dummy (sentinel) node: put a fake node before the head. Then inserting or removing the first real node follows the same code as any other node, which removes a whole class of special cases.
- Pointer to a node, not to a value: when you write
cur.next = cur.next.nextyou are changing which node a reference points at. The skipped node is not modified; it simply becomes unreachable and the garbage collector reclaims it.
The three patterns worth memorizing:
- Reverse: walk once, and for each node save
next, flipnode.nextto point at the previous node, then advance. Three moving references (prev,cur,next), O(n) time and O(1) space. - Fast and slow pointers (Floyd):
slowmoves one step andfastmoves two. If there is a cycle,fasteventually lapsslowand they meet. Iffastreaches the end, there is no cycle. The same trick finds the middle: whenfasthits the end,slowis halfway. - Dummy node plus a trailing pointer: used for deleting by value, merging sorted lists, and removing the n-th node from the end (advance one pointer n steps ahead first).
Reversing is easiest to see as arrows flipping one at a time. Step through reversing 1 -> 2 -> 3 -> 4; the green node is cur and the amber node is prev.
Reverse in place: each step flips one arrow, using only three references (prev, cur, next).
Fast and slow pointers can find the middle. Using the list 5 -> 4 -> 2 -> 1 from the code below, slow moves one node per step and fast moves two.
When fast falls off the end, slow is at the middle. With 4 nodes it lands on the second middle node, the value 2.
Now the same pointers on a list that loops back. Node 1 points to node 4, so the tail never ends.
Inside a loop the fast pointer gains one node per step on the slow pointer, so it must eventually land on it.
| Operation | Time | Notes |
|---|---|---|
| Access i-th item | O(n) | Must walk from the head |
| Insert / delete at head | O(1) | Rewire head |
| Insert / delete after a known node | O(1) | Singly: delete needs the previous node |
| Search by value | O(n) | No random access, no binary search |
| Append | O(1) with tail pointer | O(n) without it |
| Reverse / cycle check / find middle | O(n) time, O(1) space | One pass with a few references |
Code: reverse, delete, middle and cycle detection
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
def from_list(xs):
dummy = tail = Node(None)
for x in xs:
tail.next = Node(x)
tail = tail.next
return dummy.next
def to_str(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
return " -> ".join(parts)
def reverse(head):
prev = None
while head:
nxt = head.next # remember the rest
head.next = prev # flip the arrow
prev, head = head, nxt
return prev
def remove_value(head, target):
dummy = Node(None, head) # dummy node: head needs no special case
cur = dummy
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow.val
head = from_list([1, 2, 3, 4, 5])
print(to_str(head))
head = reverse(head)
print(to_str(head))
head = remove_value(head, 3)
print(to_str(head))
print(middle(head))
print(has_cycle(head))
tail = head
while tail.next:
tail = tail.next
tail.next = head.next # create a loop
print(has_cycle(head))class Node {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function fromList(xs) {
const dummy = new Node(null);
let tail = dummy;
for (const x of xs) {
tail.next = new Node(x);
tail = tail.next;
}
return dummy.next;
}
function toStr(head) {
const parts = [];
for (let n = head; n; n = n.next) parts.push(String(n.val));
return parts.join(" -> ");
}
function reverse(head) {
let prev = null;
while (head) {
const next = head.next; // remember the rest
head.next = prev; // flip the arrow
prev = head;
head = next;
}
return prev;
}
function removeValue(head, target) {
const dummy = new Node(null, head); // dummy node: head needs no special case
let cur = dummy;
while (cur.next) {
if (cur.next.val === target) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
function middle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow.val;
}
let head = fromList([1, 2, 3, 4, 5]);
console.log(toStr(head));
head = reverse(head);
console.log(toStr(head));
head = removeValue(head, 3);
console.log(toStr(head));
console.log(middle(head));
console.log(hasCycle(head) ? "True" : "False");
let tail = head;
while (tail.next) tail = tail.next;
tail.next = head.next; // create a loop
console.log(hasCycle(head) ? "True" : "False");Both versions print:
1 -> 2 -> 3 -> 4 -> 5
5 -> 4 -> 3 -> 2 -> 1
5 -> 4 -> 2 -> 1
2
False
True
The list has 4 nodes after the delete, so middle returns the second of the two middle nodes (value 2). The last two lines show cycle detection before and after we link the tail back into the list.
Common pitfalls
- Losing the rest of the list: overwriting
node.nextbefore saving it orphans every node after it. - Null dereference:
fast.next.nextcrashes whenfast.nextis null. Always checkfast and fast.nextfirst. - Forgetting the head case: deleting or inserting at the head changes what the caller holds. Use a dummy node and return
dummy.next. - Accidental cycles: after relinking nodes (for example while reversing part of a list), make sure the new tail's
nextis null. - Believing linked lists are faster than arrays for inserts: you still pay O(n) to find the position, and nodes scattered in memory hurt CPU cache behavior. In practice arrays and dynamic arrays win on most workloads.
- Comparing nodes by value: cycle detection compares node identity (
isin Python,===in JavaScript), not stored values, since duplicates are normal.
Practice
Find the middle node easy
Hint
Move one pointer twice as fast as another. Where is the slow one when the fast one finishes?
Show solution
Start slow and fast at the head. While fast and fast.next exist, advance slow by one and fast by two. When the loop ends, slow is at the middle (the second middle for even lengths). One pass, O(n) time, O(1) space, and no need to know the length.
Merge two sorted lists medium
Hint
Use a dummy node and a tail pointer, and always attach the smaller head.
Show solution
Create dummy and tail = dummy. While both lists are non-empty, attach whichever head value is smaller to tail.next and advance both that list and tail. When one list runs out, attach the remainder of the other in a single assignment. Return dummy.next. O(n + m) time, O(1) extra space, and it reuses the existing nodes.
Remove the n-th node from the end medium
Hint
You can only walk forward. Create a gap of n nodes between two pointers.
Show solution
Use a dummy node. Advance lead n steps from the dummy, then move lead and trail together until lead.next is null. Now trail.next is the node to remove, so set trail.next = trail.next.next. One pass, O(1) space. The dummy handles the case where the head itself is removed.
Find where a cycle begins hard
Hint
After the pointers meet, restart one from the head. What does moving both one step at a time reveal?
Show solution
Run Floyd's algorithm until slow and fast meet inside the cycle. Reset one pointer to the head and advance both one step at a time; they meet exactly at the cycle's entry node. Reason: if the head is a steps from the entry and the meeting point is b steps into the cycle of length c, then a is congruent to c - b modulo c, so walking a more steps from the meeting point lands on the entry. O(n) time, O(1) space.
Interview questions
- Array vs linked list? Arrays give O(1) indexing and great cache locality; linked lists give O(1) splicing when you already hold the node and never need a big contiguous block. Most real code prefers arrays.
- How do you detect a cycle without extra memory? Floyd's fast and slow pointers. A hash set of visited nodes also works but uses O(n) space.
- Why use a doubly linked list in an LRU cache? With a hash map from key to node, you can unlink any node and move it to the front in O(1), which needs the
prevpointer. - How would you reverse a list recursively? Reverse the rest, then make the next node point back at the current one and set the current
nextto null. It uses O(n) stack space, so the iterative version is safer for long lists.
Interviewers look for: using a dummy node, checking null cases (empty list, one node), saying out loud which pointers you save before rewiring, and stating O(1) space for the pointer tricks.
Quick check
In a singly linked list you hold a reference to a node X (not the head). What can you delete in O(1)?
Finished this lesson?
Further resources
- Linked list (Wikipedia) (article)
- Cycle detection (Wikipedia) (article)