Linked Lists
On this page
Arrays are great until you need to insert or remove in the middle, again and again: each change shifts everything after it. A linked list makes those changes O(1) if you already hold the right node, at the price of slow access by position. Linked list problems are common in interviews less because the structure is popular in real code and more because they test careful pointer handling under pressure.
How it works
Nodes and pointers

A singly linked list is a chain of nodes. Each node holds a value and a pointer (next) to the following node. The last node points to null. You keep a reference to the first node, the head, and reach everything else by following pointers.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Nodes don't sit next to each other in memory, so there's no way to jump to the 5th node: you walk from head, one step at a time. A doubly linked list adds a prev pointer to each node, so you can also walk backwards and remove a node in O(1) when you only hold the node itself. LRU caches use exactly that.
Insert and delete by rewiring

To insert a new node after node a:
new.next = a.nexta.next = new
The order matters. If you set a.next = new first, the rest of the list is lost. Deleting the node after a is one line: a.next = a.next.next.
The dummy head

Many bugs come from the head being special: deleting it, or inserting before it, needs different code from every other position. A dummy node placed before the head removes the special case. Do all the work from the dummy, then return dummy.next.
Operations and costs
| Operation | Singly linked | Array |
|---|---|---|
| Access the k-th element | O(k) | O(1) |
| Insert or delete at head | O(1) | O(n) |
| Insert or delete after a node you hold | O(1) | O(n) |
| Insert at tail (with a tail pointer) | O(1) | O(1) amortized |
| Search for a value | O(n) | O(n) |
| Extra memory per element | one pointer (two if doubly linked) | none |
When to reach for it
In interviews, you are usually handed a linked list rather than choosing one. Choose one yourself when:
- You need O(1) insert and delete at both ends or in the middle, and you keep references to nodes (a doubly linked list plus a hash map gives an LRU cache).
- You are merging or splicing sequences without copying them.
Most linked list problems use a small set of techniques:
- Dummy head for anything that might change the first node.
- Two pointers, slow and fast: find the middle, detect a cycle, find the k-th node from the end.
- Reverse in place with three pointers (
prev,curr,next). - Merge two sorted lists by always attaching the smaller head.
Example
Remove every node with a given value. With a dummy head, the first node needs no special handling:
def remove_value(head, target):
dummy = ListNode(0, head)
prev = dummy
while prev.next:
if prev.next.val == target:
prev.next = prev.next.next # unlink, stay on prev
else:
prev = prev.next
return dummy.next
ListNode removeValue(ListNode head, int target) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while (prev.next != null) {
if (prev.next.val == target) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return dummy.next;
}
ListNode* removeValue(ListNode* head, int target) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
while (prev->next) {
if (prev->next->val == target) {
prev->next = prev->next->next; // free the node here if you own it
} else {
prev = prev->next;
}
}
return dummy.next;
}
func removeValue(head *ListNode, target int) *ListNode {
dummy := &ListNode{Next: head}
prev := dummy
for prev.Next != nil {
if prev.Next.Val == target {
prev.Next = prev.Next.Next
} else {
prev = prev.Next
}
}
return dummy.Next
}
Time: O(n). Space: O(1). With input 3 → 7 → 3 → 1 and target 3, the result is 7 → 1; with 3 → 3 it's an empty list, and the dummy makes that case work without extra code.
Finding the middle uses slow and fast pointers: fast moves two steps for every one step of slow, so when fast reaches the end, slow is in the middle.
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow # for an even length, the second of the two middles
Common mistakes
- Losing the rest of the list. Save
nextbefore you overwrite a pointer. - Null checks.
fast.next.nextcrashes iffast.nextis null. Checkfast and fast.nextin the loop condition. - Forgetting the head case. Without a dummy, deleting the first node or inserting before it needs separate code.
- Moving
prevafter a deletion. After unlinking a node, stay onprev, or you will skip the next match. - Returning the wrong head. After reversing or with a dummy, the head has changed; return the new one.
- Cycles in your own code. A wrong pointer update can create a loop and your traversal never ends. Draw three nodes and trace each assignment.
Say this in the interview
- "I'll add a dummy node before the head so deleting the first node isn't a special case."
- "I'll save
curr.nextbefore I change it so I don't lose the rest of the list." - "Slow and fast pointers find the middle in one pass with O(1) space."
Used in
- Pattern: Linked List Techniques
- Problems: Reverse Linked List, Merge Two Sorted Lists, Linked List Cycle, Remove Nth Node From End of List, LRU Cache, Merge k Sorted Lists
- Data structures: Arrays and Strings (the opposite trade-off), Stacks and Queues (often built on linked lists)