The Linked List
Every node stores one value and the address of the next node. A linked list gives up contiguous memory and index access. What it gets back: when you already hold the node in front of a position, inserting or deleting there is two reference writes and nothing moves.
Intuition: stop moving elements, store the address instead
A linked list is built for exactly the operation an array is bad at.
Recall the most expensive moment in the array chapter. Inserting one element in the middle of an array moves every element to the right of it one slot further right. Deleting one moves them all back. With a hundred thousand elements and operations landing in the middle, that O(n) copying is a real cost. There is one cause: an array ties logical order to physical order. Two neighbors are neighbors in memory, so there is no room between them.
A linked list removes that tie. An element no longer has to live next to its neighbor. Instead each element carries a note that says where the next one is. You are given the first address (head), you follow the note to the second element, then the next, and so on. When a note holds nothing (null), the list is over.
In that world, inserting C between A and B is cheap: write “next is B” into C, then change the note in A to “next is C”. Two notes change and no other element is touched. The price is the house number. To reach the hundredth element you have to follow ninety-nine notes from the start. Three rules follow from this:
Nodes may sit anywhere in memory, far apart from each other. The benefit: no large contiguous block is needed, and the list never has to be copied into a bigger space. The cost: the CPU cannot guess where the next node is, so it cannot load it in advance.
Each node is one value plus one next reference. The order of the list exists only in those references and has nothing to do with the addresses. That chain of references is what the word “linked” refers to.
There is no “address = base + i × size” formula here. Reaching element i means starting at head and following i references, so access is O(n). That is what a linked list pays for cheap insertion and deletion.
Where linked lists are actually used
A memory allocator keeps its unused blocks in a free list, so a freed block is returned by rewriting two references instead of moving memory. The FAT file system stores each file as a chain of blocks, where every block records the number of the next one, which is why a file can be spread over a whole disk. And the best known interview combination, the LRU cache (LC 146) = a hash map + a doubly linked list, exists because a node reference taken from the hash map can be unlinked and relinked in O(1). Chapter 13 builds one.
In memory: scattered nodes and invisible lines
The same values stored two ways, and why a linked list can never have O(1) index access.
Introduction §03 said it already: a reference is a memory address, a note that says “the object is at 2096”. A linked list node is nothing more than a value and such a note packed together. The figure shows the same values [7, 2, 9] stored twice. Notice that the physical order of the three nodes (2096 → 3120 → 1432) and their logical order (7 → 2 → 9) are unrelated:
The O(1) of an array comes from the address formula, and that formula works only because the elements are contiguous and all the same size. Linked list nodes are scattered, and the address of node i is recorded only inside node i−1. To learn where it is you must first reach the one before it. Where the information is kept decides how it can be read: O(n) is not a weak implementation, it follows from the structure.
{ val: 7, next: 1432 } — one slot for the value, one slot for an address. In Java, Python, and JavaScript, next is a reference to the next node object. When there is no next node it holds null / None / null. That is the end of the list, and also the first place to look when a null reference error appears.
Why a linked list is often slower than the complexity suggests
The array chapter described the cache line: reading arr[0] brings arr[1..15] into the cache at the same time, because they are next to it. A linked list gets nothing from that. The address of the next node is known only after the current node has been read, so the CPU cannot load it in advance, and almost every step can be a cache miss that goes to main memory. Both structures still traverse in O(n). The difference is a constant factor, not a different complexity, but it is a large constant: on real hardware, walking an array is commonly several times faster. The practical rule: reach for the array family by default, and use a linked list when you really need O(1) insertion or deletion at a node you already hold.
Core operations: rewriting references is cheap, finding the place is not
Every O(1) here comes with a condition. The key animation: connect before you disconnect.
| Operation | Complexity | Why |
|---|---|---|
| Read element i / search by value | O(n) | There is no address formula, so you follow next from head one node at a time. |
| Insert / delete at the front | O(1) | head is already in your hand: one or two reference writes, independent of the length. |
| Insert / delete when you already hold the predecessor | O(1) | Two writes to insert, one to delete — only if the predecessor is already in your hand. This single line is where the whole value of a linked list comes from |
| Insert / delete at position i | O(n) | O(n) to walk to the predecessor plus O(1) to rewrite references. The cost is in the walking, not the rewriting. |
| Append at the end (with a tail reference) | O(1) | tail points at the last node already. Without a tail reference you have to walk the whole list, which is O(n). |
The third row carries the condition that matters most. “Insertion and deletion in a linked list are O(1)” is repeated far too often without it. The full version is: rewriting the references is O(1), and finding which references to rewrite is O(n). So a linked list wins when the predecessor, or the node itself, is already in your hand: deleting during a traversal you are already performing, or an LRU cache where a hash map hands you the node.
Inserting takes only two steps, but the order of the two decides whether the list survives. Connect before you disconnect: the new node takes hold of the successor first (newNode.next = cur), and only then does the predecessor switch over (prev.next = newNode). What happens if you swap them? The lab below has a button that does it, so you can lose the second half of a list once and remember it:
Deleting a node when the node is all you have
Deleting node X normally needs the node before it, so that its next can be moved past X. If all you are given is X itself, there is a trick (LC 237): copy the value of X.next into X, then delete X.next instead. The list ends up with the right sequence of values in O(1). Two limits come with it. It does not work when X is the last node, because there is no following value to copy and no way to reach the node before X. And the node object that survives is not the one the caller pointed at, so any other reference to X.next now points at a node that is no longer part of the list.
Three bugs that account for most linked list mistakes
(1) Disconnecting before connecting: the second half of the list loses its last reference, as the lab just showed. (2) Reading a field of null: taking .next of a null reference. Test for null first, in the right order (cur != null && cur.next != null; swapping the two tests reintroduces the crash, because && evaluates the left side first and only then the right). (3) Forgetting the special case for the head: when you delete or insert at the front there is no predecessor to rewrite. The dummy node in §04 removes that case. Experienced programmers all do the same thing before writing linked list code: draw the nodes and put the pointer writes in order on paper first.
Build one: a singly linked list, a doubly linked list, and a dummy node
A working linked list from nothing, commented line by line in three languages.
A complete singly linked list. It keeps three fields: head, tail, and size. tail brings appending down to O(1), and size brings the length query down to O(1). Both are small decisions that spend a little space to save time. Every method follows the same shape: find the predecessor, then rewrite references:
is None, not == None. The multiple assignment prev, cur = cur, nxt evaluates the whole right side first, which fits reversal well. Do not compress all three steps into one line though; readability comes first.A doubly linked list adds the way back. Each node carries one more reference, prev, so you can move in both directions from any node. Two things follow. (1) Deleting no longer needs a search: the node already knows its predecessor, so holding the node is enough to delete it in O(1). That is what makes an LRU cache work. (2) You can walk from the tail to the head. The price: one more reference per node, and every insertion or deletion now rewrites four references, which is easier to get wrong:
A dummy node removes a whole class of bugs. You may have noticed the extra branch for i == 0 in insertAt and removeAt above. Here is the exact reason: no node points at the head. The general rule “rewrite the next field of the predecessor” has nothing to rewrite, so the front has to be handled by assigning to the head variable itself. A dummy node (also called a sentinel) fixes that by placing one fake node in front of the head, so every real node has a predecessor. Compare two versions of the same problem (LC 203, delete every node whose value equals val):
When should you use a dummy node?
One test: use a dummy whenever the head of the answer may change — deleted, inserted before, or relinked. Deletion problems (LC 203, 19), problems that build a new list (LC 21, 2), and problems that rearrange a range (LC 92, 24, 25) almost all qualify. The cost is one temporary node. What you get is one branch fewer and one class of bug fewer, the kind that only appears when the operation happens to touch the head. Remember to return dummy.next rather than head.
Three languages: none of them gives you a singly linked list
For interview problems you write ListNode yourself, and Java LinkedList has a well known trap.
A fact that may surprise you: none of the three languages has a built-in singly linked list that you would use for interview problems. The reason is the engineering rule from §02. For general use a dynamic array is almost always faster, and the cases where a singly linked list is worth it are usually special enough to be worth writing by hand. So in problem solving, a linked list is just an agreed ListNode shape that LeetCode defines for you:
next shadows the built-in next() function inside that method. LeetCode writes it this way, but rename it in your own code.| Topic | Java | Python | JavaScript |
|---|---|---|---|
| Built-in singly linked list | None (write ListNode yourself) | None (same) | None (same) |
| Default sequence type | ArrayList (dynamic array) | list (dynamic array) | Array (dynamic array) |
| Closest thing in the standard library | LinkedList (doubly linked, implements List and Deque) | collections.deque (doubly linked list of blocks, nodes not exposed) | None |
| O(1) at both ends | addFirst / addLast / pollFirst / pollLast | appendleft / append / popleft / pop | Only at the end (push/pop); shift/unshift at the front are O(n) |
| The biggest trap | get(i) is O(n) — do not treat it as an array | deque[i] in the middle is O(n) as well | Using an array as a queue and forgetting that shift is O(n) |
A classic Java accident: using LinkedList like ArrayList
for (int i = 0; i < list.size(); i++) list.get(i) costs O(n) on an ArrayList and O(n²) on a LinkedList, because each get(i) walks i steps from the head, or from the tail when that end is closer. With a hundred thousand elements the first finishes in milliseconds and the second takes many seconds. Traverse a LinkedList with a for-each loop or an iterator instead: they follow next once, so the whole pass is O(n). A more practical piece of advice comes from Joshua Bloch, who wrote the class and has said he does not use it himself. Use ArrayDeque when you need a queue and ArrayList when you need a list; both are usually faster.
Why Python deque is a linked list of blocks
collections.deque is not the textbook linked list with one element per node. Each node holds a small array of 64 slots, and the blocks are linked to each other in both directions. It is a compromise between an array and a linked list: both ends stay O(1), while 64 elements share one allocation and sit next to each other in memory, so the CPU cache works for most of the steps. That removes a large part of the cache problem described in §02. Real linked structures in production code often look like this.
Three patterns: reversal, fast and slow pointers, dummy node
★ Interview coreAlmost every linked list problem is a combination of these three. Three worked examples, one step at a time.
Array problems are usually about finding a clever order to visit the elements. Linked list problems are about getting the order of the pointer writes exactly right. The good news is that the patterns are few. Once these three are familiar, you have a way into all eleven problems in this chapter:
prev, cur, and nxt turn the references around one at a time. Reversing a whole list (206), a range (92), or every group of k (25) are all variations of the same loop. This is the most basic linked list operation there is.
Two pointers moving at different speeds keep a controlled gap. Fast moves 2 and slow moves 1: find the middle (876) or detect a cycle (141, 142). Move fast n nodes ahead first and the gap stays n: the nth node from the end (19). With the loop condition fast != null && fast.next != null, an even-length list leaves slow on the second of the two middle nodes.
Might the head change? Put a dummy in front of it, so every node has a predecessor and the special case disappears. It is the standard opening for deletion (203, 19), for building a new list (21, 2), and for rearranging a range (24, 92, 25).
LC 206 · Reverse Linked List
EASYThe problem: reverse a singly linked list and return the new head. Brute force: copy the values into an array, reverse the array, copy them back. That needs O(n) extra space, and copying values does not work at all when a node carries a large object. The intended solution: change no values, and turn each next reference around in place. The difficulty is that the moment you overwrite cur.next, the way to the rest of the list is gone, so every round has to save it first. Three pointers, three steps per round: save, turn, advance:
prev = null, cur = head. prev is the head of the part that is already reversed, cur is the node being processed. The goal is to turn every next reference around in place, without creating a single new node.Complexity and the usual follow-up questions
Time O(n), one visit per node. Extra space O(1), three pointer variables. Follow-up one: why return prev and not cur? The loop ends when cur is null, and at that moment prev is standing on the last node of the original list, which is the head of the reversed one. Follow-up two: how would you write it recursively? reverseList(head.next) reverses the rest first, then head.next.next = head attaches head to the end, and head.next = null closes the list. It reads well, but the call stack holds one frame per node, so the space is O(n), not O(1), and a long list can exhaust the stack. The iterative version is the safer answer.
LC 141 · Linked List Cycle
EASYThe problem: decide whether a list contains a cycle, that is, whether some node’s next points back to an earlier node. Traversing a list with a cycle never ends, so this is the first suspect whenever linked list code hangs. Brute force: record every node you have seen in a hash set; seeing one twice means there is a cycle. That is O(n) time but O(n) space. The intended solution: Floyd’s cycle detection, also called the tortoise and the hare. Two pointers start together; slow moves one node per step and fast moves two. Without a cycle, fast reaches null first. With a cycle, fast catches slow inside it:
Why must they meet, and why exactly twice the speed?
Measure the distance from fast forward along the cycle to slow. Once both are inside the cycle, that distance is a whole number that is never negative. Every step, fast advances 2 and slow advances 1, so the distance drops by exactly 1. A whole number that decreases by 1 each step must reach 0, and 0 means both pointers are on the same node. There is no way to step over each other. That also answers “why not three times as fast”: with a relative speed of 2 the distance drops by 2 and can pass over 0 without ever equalling it. Two pointers starting from the head still meet in that case, but showing it needs modular arithmetic rather than this one-line argument. The relative speed 1 version has the cleanest proof and the clearest bound: after slow enters the cycle, they meet within one lap.
Complexity and the usual follow-up question
Time O(n), extra space O(1), against the O(n) space of the hash set version. The follow-up you should expect: how do you find where the cycle starts? (LC 142) After they meet, move one pointer back to head and advance both one node per step; the node where they meet again is the entrance. Behind it is the equation “distance from head to the entrance = distance from the meeting point round to the entrance, plus a whole number of laps”, which follows from “fast travelled twice as far as slow”. Get the meeting argument of 141 straight first; 142 is then one step of algebra.
LC 21 · Merge Two Sorted Lists
EASY+The problem: two lists sorted in increasing order, merged into one sorted list by relinking the existing nodes, not by creating new values. The idea: the same as merging two sorted piles of paper. Compare the top sheet of each pile and move the smaller one to the result. The comparison is not the hard part. Deciding which node becomes the head of the result is — it may come from l1 or from l2. Rather than writing branches for that, start with a dummy node and let tail append after it:
Complexity and the usual follow-up questions
Time O(n + m), each node is attached once. Extra space O(1): two variables, dummy and tail, and every node is reused. Look at the last line, tail.next = l1 or l2. Attaching the whole remaining segment of a linked list is a single pointer write, O(1); merging arrays would have to copy those elements. The follow-up to expect: what about K lists? (LC 23, Hard) Merging them one pair at a time is O(nK); taking the smallest of the K current heads from a min-heap gives O(n log K), which is covered in the heap chapter (chapter 09). This merge step is also the core of merge sort, which is how a linked list is sorted (LC 148).
Problem set: 11 linked list problems
Hot 100 selectionDeletion, then fast and slow pointers, then dummy nodes, then reversal combinations. Your checkmarks are stored locally.
Quiz
✎ QuizAnswer all 7 correctly to light up this chapter.
Under what condition is it true that inserting into or deleting from a linked list is O(1)?
You are inserting a new node between prev and cur. What is the correct order of the two pointer writes?
Cycle detection: once both pointers are inside the cycle, why must the fast pointer meet the slow one instead of stepping over it?
In which situations should you prefer an array over a linked list? (Select all that apply)
Java's LinkedList is a doubly linked list. What is the time complexity of list.get(i)? (Answer in O(...) form)
What does a dummy (sentinel) node actually do?
There are two ways to find the middle of a list: (1) count the length n, then walk n/2 steps; (2) fast and slow pointers in one pass. Which statement is correct?
- A linked list is nodes of value + next reference scattered in memory. The order lives only in the references, so there is no address formula and access and search are O(n). In exchange it needs no contiguous block and never has to be copied to grow.
- The full version of “insertion and deletion are O(1)”: rewriting the references is O(1), finding the predecessor is O(n). The real use is when the node reference is already in your hand, as in an LRU cache (hash map + doubly linked list).
- Pointer rule: connect before you disconnect (
newNode.next = curfirst,prev.next = newNodesecond). Reversed, the whole second half of the list loses its last reference. Save the next node before you overwrite a next field. - Three patterns: three-pointer reversal (save, turn, advance), fast and slow pointers (relative speed 1, so the gap drops by 1 per step and a meeting is unavoidable inside a cycle), and the dummy node (every node gets a predecessor, so the head needs no special case).
- Choosing and language traps: prefer the array family by default, because it is cache friendly. None of the three languages has a built-in singly linked list, so you write ListNode yourself. Java LinkedList.get(i) is O(n), which makes an index loop O(n²); it is a deque, not an array.