Linked lists
Data structuresHigh priority~1 hNodes chained by pointers — O(1) insert/delete at a known spot, but no O(1) random access.
Definition
A linked list is a chain of nodes, each holding a value and a next pointer to the following node (the last points to null). Nodes aren't contiguous in memory, so there's no base + i trick — reaching position i means walking i links. The payoff is cheap structural edits: splicing a node in or out is a couple of pointer reassignments, no shifting.
the chain 1 -> 2 -> 3, and what a head-insert costs
A list is just nodes joined by `next` links; the tail's `next` is `null`. There's no index — to reach a node you follow arrows from the head.
`head` names the first node. Everything you do starts from the pointer you hold.
To prepend a value, point the new node's `next` at the current head — no elements move.
Operations
| Operation | Average | Worst | Note |
|---|---|---|---|
| access / search by value | O(n) | O(n) | walk from the head |
| insert / delete at head | O(1) | O(1) | |
| insert / delete after a known node | O(1) | O(1) | just relink pointers |
| find then delete | O(n) | O(n) | the find dominates |
When to use
Reach for a linked list when you insert or delete at the ends or at a node you already hold — those are O(1) pointer relinks, where an array would shift O(n) elements. It also underlies queues and stacks. In interviews the prompt usually hands you a list; the skill being tested is pointer surgery — reverse it, find a node from the end, detect a cycle, splice two together — under O(1) extra space. Skip linked lists when you need random access or tight cache-friendly iteration: an array's contiguity wins there.
Techniques
Dummy head — allocate a throwaway node before the real head and build off it, so prepending or deleting the first node needs no special case; return dummy.next at the end (merge two lists, remove the kth-from-end, partition).
Three-pointer reversal — carry prev, curr, and a saved next; flip curr.next to prev, then slide all three forward. This rewires the list in place in one pass (reverse a list, reverse a sublist).
Fast / slow pointers — advance fast two nodes for every one of slow. When fast reaches the end slow sits at the midpoint; if the two ever meet, there's a cycle. The basis for the midpoint, cycle, and palindrome checks.
Two-pass gap — to act on a node measured from the end, send one pointer k nodes ahead, then move both together; when the leader hits the end, the follower is k from the end (remove nth from end).
Related structures
Linked list vs array
Arrays give O(1) indexing and better cache locality; linked lists give O(1) insert/delete at a known node and grow without reallocating. The recurring interview tells are a dummy head node (to dodge empty-list edge cases) and the prev/curr/next three-pointer dance for reversing in place. The fast/slow trick is shared with two-pointers — same idea, applied to nodes instead of indices.
Implementation
// const node = { val: 1, next: null };
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next; // save before we overwrite it
curr.next = prev; // flip this link backwards
prev = curr; // advance both pointers
curr = next;
}
return prev; // new head
}Worked examples
Merge Two Sorted Lists — splice two sorted lists into one sorted list. A dummy head lets us append without special-casing the first node; we repeatedly attach the smaller head and advance that list, then tack on whatever remains. Here's 2 -> 4 merged with 1 -> 3:
tail builds the merged list a -> b: [2, 4] and [1, 3]
`d` is the dummy head. Heads are 2 and 1; 1 is smaller, so attach it and advance `b`.
tail now ends at 1. Heads are 2 and 3; 2 is smaller, attach it and advance `a`.
Heads are 4 and 3; 3 is smaller, attach it and advance `b` — list b is now exhausted.
One list is empty, so attach the entire remaining list a (just 4). Done.
Result: 1 -> 2 -> 3 -> 4. Return `dummy.next`, skipping the throwaway head.
function mergeTwoLists(l1, l2) {
const dummy = { val: 0, next: null }; // fake head to append onto
let tail = dummy;
while (l1 && l2) {
// attach the smaller node, then advance that list
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = l1 ?? l2; // one list is now empty; attach the rest
return dummy.next;
}Each node is attached exactly once and every step is O(1), so the merge is O(n + m) time and O(1) extra space — the output reuses the existing nodes rather than copying them.
Things to look out for
- Save
curr.nextbefore you overwrite it — once you setcurr.next = prev, the rest of the list is gone unless you stashed it. - Use a
dummyhead whenever the head node itself might change (a delete at position 1, a merge); it removes a whole class of null-head special cases. - Always check
nodeandnode.nextbefore readingnode.next.next— the classic fast-pointer null dereference. - Return the new head, not the old one. After a reversal the original
headis the tail; returning it loses the list.
Corner cases
- Empty list (
head === null). - Single node — many two-pointer setups must still behave (a one-node list is its own reverse and a trivial palindrome).
- Two nodes — the smallest case where
slow/fastand pair-swaps actually move. - Operating at the head vs. the tail (the dummy-head case vs. the run-off-the-end case).
- All-equal values, which read as palindromes and stress dedup logic.