A sequence stored as nodes
A Python list keeps its items in consecutive slots of memory. Reading the item at position takes one step, but inserting at the front does not: a.insert(0, x) first moves every item one slot to the right.
If a million values are stored that way and we insert 100,000 more at the front, one at a time, each insert moves about a million items. In all we move about
Each move is cheap, but when we ran this in Python it took about 26 seconds.
A linked list stores the same sequence in a different way. Each value sits in its own small object, called a node, and each node also holds a link to the node that comes after it. Inserting at the front then means making one node and linking it to the old first node, however long the list is, so the 100,000 inserts are 100,000 short steps.
Compared with an array such as a Python list, a linked list gives up fast access by position: there is no way to jump to the item at position without following links from the first node. In exchange, a program that holds a node can insert a new node after it, or remove the node after it, in constant time, wherever that node sits in the list.
The list 4, 9, 2
Here is the list 4, 9, 2, which we use for most of the lesson. Each circle is a node and each arrow is a link. A program holds a list by holding its first node, the head. The last node has no node after it, so its link is null, a value that stands for no node. The head of an empty list is null as well.
From here on we write this list as 4 → 9 → 2.
Build a list and walk it
In Python a node is an object with two fields, val for the value and next for the link, and the null link is None. The program below builds 4 → 9 → 2 one node at a time and prints its values:
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def print_list(head):
values = []
node = head
while node is not None:
values.append(node.val)
node = node.next
print(values)
head = Node(4)
head.next = Node(9)
head.next.next = Node(2)
print_list(head)Prints [4, 9, 2]. The later listings use this Node class.
print_list moves along the list the way every walk in this lesson does. node starts on the head, and the line node = node.next changes nothing in the list: it makes the name node refer to the following node. After the last node, node is None and the loop ends.
A walk like this is the only way to get anywhere in a linked list. Reaching the third node means following two links from the head, and counting the nodes means walking to the end, because a linked list does not store its length.
Insert and delete by changing links
To insert 7 after the node holding 4 in 4 → 9 → 2, no node has to move. We make a node for 7 and change two links:
- Point the new node at the node that follows 4, which is 9.
- Point the node holding 4 at the new node.
The list is now 4 → 7 → 9 → 2. The two steps have to run in this order, because step 2 overwrites the link out of 4, and before step 1 that link is the only record of where 9 is. If step 2 ran first, step 1 would copy a link that already leads to the new node: 7 would be linked to itself, and nothing would lead to 9 or 2.
Deleting takes one link change. To delete 7, the node after 4, we point 4 at the node two places along, which is 9. No link leads to 7 any more, so a walk from the head skips it, and the list is 4 → 9 → 2 again.
def insert_after(node, val):
new = Node(val)
new.next = node.next
node.next = new
def delete_after(node):
node.next = node.next.nextWith head on 4 → 9 → 2, insert_after(head, 7) makes it 4 → 7 → 9 → 2, and delete_after(head) then makes it 4 → 9 → 2 again.
Both functions need the node before the change, and the head has no node before it. A change at the front therefore goes to the variable head and not to a link: inserting at the front makes a new node that links to the old head and becomes the head, and deleting the first node makes the second node the head. Code that edits a list has to handle the front as a special case, unless it puts an extra node before the head, as the merge further down does.
Costs of an array and a linked list
| Operation | Array | Linked list |
|---|---|---|
| Read the item at position | : follow links | |
| Insert or delete at the front | : every item shifts | : the head changes |
| Insert or delete after a node we hold | : the items after it shift | : one or two links change |
| Append at the end | amortized | to walk there, or if we keep the last node in a variable |
In a linked list the costly part of an operation is finding the node; once we hold it, an insertion or deletion next to it takes constant time. In an array it is the other way round: any position is found in one step, but inserting or deleting there shifts the items after it.
So the linked list is faster only when the program already holds the node next to the change, because finding a node by its position or its value is itself an walk. An array is the default for a sequence, and a linked list suits a program that keeps references to its nodes, in a hash map for example, and often moves or removes them.
Deeper read: doubly linked lists
The lists in this lesson are singly linked: each node has one link, to the node after it. To delete a node we therefore need the node before it, and if all we hold is the node itself, finding its predecessor takes a walk from the head.
A doubly linked list gives each node a second link, prev, to the node before it. A node can then be removed given nothing but the node itself, by linking its two neighbours to each other:
class DNode:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def unlink(node):
node.prev.next = node.next
node.next.prev = node.prevIn 4 ⇄ 7 ⇄ 9, calling unlink on the node 7 leaves 4 ⇄ 9.
unlink assumes that the node has a neighbour on each side. The first and last nodes do not, so each end would need code of its own. The usual remedy is a spare node at each end of the list, with a value that is never read. With the two spares in place, every real node has both a prev and a next, and unlink works on any of them. The cache in the next lesson is built this way.
Reverse a list by turning its links around
Inserting and deleting change one or two links. Reversing a list changes every link, and harder list problems, such as Reorder List at the end of this lesson, use it as one of their steps.
You get the head of a singly linked list. Reverse the list and return the head of the reversed list.
Constraints
- The list has between 0 and 5,000 nodes
Sample 1 · Input
head = [1,2,3,4,5]
Output
[5,4,3,2,1]
Sample 2 · Input
head = [1,2]
Output
[2,1]
Sample 3 · Input
head = []
Output
[]
LeetCode writes a list as its values from head to tail, and its node type, ListNode, has the same two fields as our Node.
The direct way is to copy the values into an array and build a new list from the array read backwards. The judge accepts that, but it makes new nodes and uses extra memory. Turning the links of the existing nodes around needs only a constant amount of extra memory, and that is the version we write here.
Take our list 4 → 9 → 2. Reversed, it is 2 → 9 → 4: 2 links to 9, 9 links to 4, 4 links to null, and 2 is the head. But each link we change is also our only way forward. If we set the link of 4 to null first, nothing leads to 9 any more.
So we walk the list once with two variables. prev is the head of the part that is already reversed, and cur is the head of the part not yet touched. At the start prev is null and cur is the head. Each turn of the loop moves the node cur from the front of the untouched part to the front of the reversed part, in four steps:
- Save the node after
curin a third variable,nxt, because the next step overwrites the only link to it. - Point the link of
curatprev. The nodecuris now the first node of the reversed part. - Move
prevontocur. - Move
curontonxt.
4 → 9 → 2, one row per turn of the loop. The violet nodes are the reversed part, whose links point back.The first turn saves 9, points 4 at null and moves prev onto 4. The second turn saves 2 and points 9 back at 4. In the third turn there is no node after 2, so nxt is null; the turn points 2 back at 9, and cur becomes null. The loop stops there with prev on 2, the head of 2 → 9 → 4.
The reversal loop
In code, the body of the loop is the four steps, one line each:
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def reverse(head):
prev, cur = None, head
while cur is not None:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
def build(values):
head = None
for val in reversed(values):
head = Node(val, head)
return head
def print_list(head):
values = []
while head is not None:
values.append(head.val)
head = head.next
print(values)
for values in [[1, 2, 3, 4, 5], [1, 2], []]:
print_list(reverse(build(values)))Prints the three samples' answers: [5, 4, 3, 2, 1], [2, 1] and [].
build makes a list from an array for the test. reverse returns prev and not head: after the loop, head still refers to the old first node, which is now the last one.
An empty list needs no separate case: cur starts as null, the loop does not run, and the function returns prev, which is null.
No node is lost on the way, because step 1 keeps hold of the untouched part before step 2 cuts cur away from it. The loop runs once for each node and uses three variables, so reversal takes time and extra memory.
Put the four lines in order
In this widget you run the loop on 4 → 9 → 2 yourself, by choosing which of the four lines runs next. Try cur.next = prev first to see which nodes it would cut off.
Deeper read: reverse a list recursively
LeetCode's follow-up asks for a recursive version as well. A recursive function on a linked list handles two cases, an empty list or a first node and the rest, and reversal can be written the same way: reverse everything after the first node, then attach the first node to the end of the result. A list of zero or one nodes is already its own reverse, so the function returns it unchanged.
def reverse_recursive(node):
if node is None or node.next is None:
return node
head = reverse_recursive(node.next)
node.next.next = node
node.next = None
return headOn 4 → 9 → 2, the call on 9 returns 2 → 9; then 9 is pointed back at 4, and 4 at nothing.
The base case returns the old last node, and every call passes it up unchanged as head, the head of the reversed list. node.next.next = node does the attaching. When the recursive call returns, node.next is still the old second node, and that node is now the last one of the reversed rest. Setting its link to node puts the first node after it, and node.next = None makes the first node the new end of the list.
The recursion makes one call per node, so its call stack grows to frames, where the loop used three variables. Python stops a program whose call stack passes 1,000 frames unless the limit has been raised, so with the default setting reverse_recursive fails with a RecursionError on a list of about 1,000 nodes or more, and the problem allows 5,000. The loop has no such limit.
Merge two sorted lists with a dummy node
Merge sort merges two sorted arrays by repeatedly taking the smaller of the two front values. Two sorted linked lists merge by the same rule, and nothing has to be copied: the nodes are relinked into one list.
You get the heads of two linked lists, each sorted in nondecreasing order. Splice their nodes together into one sorted list and return its head.
Constraints
- Each list has between 0 and 50 nodes
Sample 1 · Input
list1 = [1,2,4], list2 = [1,3,4]
Output
[1,1,2,3,4,4]
Sample 2 · Input
list1 = [], list2 = []
Output
[]
Sample 3 · Input
list1 = [], list2 = [0]
Output
[0]
Take the first sample, 1 → 2 → 4 and 1 → 3 → 4. The merge keeps three variables: a and b on the first node not yet merged in each list, and tail on the last node of the merged list. Each step compares the values at a and b, links the node with the smaller value after tail, and moves tail and that list's variable one node on.
At the first step the merged list is still empty, so there is no node for tail to be on. The usual way out is a dummy node: an extra node placed before the first node of the merged list as a placeholder, whose value is never read. tail starts on the dummy, so even the first real node has a node to be linked after, and no step needs a special case. When the loop ends, the head of the answer is the node after the dummy.
The dummy is the node before the head that insert_after and delete_after were missing. With the dummy written D, the merge runs like this:
a b node taken merged list1 1 a D → 12 1 b D → 1 → 12 3 a D → 1 → 1 → 24 3 b D → 1 → 1 → 2 → 34 4 a D → 1 → 1 → 2 → 3 → 4Now the first list is used up. What is left of the second, its last node 4, is at least as large as everything merged so far, so the remainder is linked after tail in one step. The node after the dummy is the head of 1 → 1 → 2 → 3 → 4 → 4.
def merge_two_lists(a, b):
dummy = tail = Node(0)
while a is not None and b is not None:
if a.val <= b.val:
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a if a is not None else b
return dummy.nextMerging 1 → 2 → 4 with 1 → 3 → 4 returns the head of 1 → 1 → 2 → 3 → 4 → 4.
On equal values, <= takes the node from the first list. The 0 in Node(0) is never read, so any value would do.
Empty lists need no code of their own. In the third sample the first list is empty, so the loop does not run, and the last line links the second list, the single node holding 0, after the dummy.
Each front node holds the smallest unused value of its list, so the smaller front is the smallest unused value overall, and linking it next keeps the result sorted. The loop runs at most times for lists of and nodes, so the merge takes time, and the dummy is the only node it creates.
Find the middle with fast and slow pointers
An array finds its middle item by halving its length. A linked list cannot jump to a position and does not store its length, so even finding the middle takes a walk.
You get the head of a linked list. Return its middle node; when the length is even there are two middle nodes, and you return the second. The judge prints the list from the node you return to the end.
Constraints
- The list has between 1 and 100 nodes
Sample 1 · Input
head = [1,2,3,4,5]
Output
[3,4,5]
Sample 2 · Input
head = [1,2,3,4,5,6]
Output
[4,5,6]
One way is to walk the list twice: once to count its nodes, and once more to follow links from the head. With two variables that move at different speeds, one walk is enough.
slow moves one node per step and fast moves two, and both start on the head. A variable that refers to a node is usually called a pointer, and this pair is known as fast and slow pointers. On the first sample, 1 → 2 → 3 → 4 → 5, they move like this:
After steps slow has followed links and fast has followed , so fast is twice as far from the head as slow. When fast is on the last node, slow is halfway there, on the middle node 3. On the second sample, 1 → 2 → 3 → 4 → 5 → 6, there is one more step: slow moves to 4, and fast moves past the last node to null. Of the two middle nodes, 3 and 4, slow is on the second, which is the one the problem asks for.
def middle_node(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slowOn 1 → 2 → 3 → 4 → 5 → 6, middle_node returns the node holding 4.
The loop condition has two tests because a step of fast follows two links. fast is not None makes sure there is a node to step from, and fast.next is not None makes sure the first of the two links leads to a node. When either test fails, fast is on the last node or past it, and slow is on the middle. The walk takes steps.
Detect a cycle with fast and slow pointers
Every list so far has ended in a null link. If the last node links back to an earlier node instead, the list has a cycle: a walk goes around the same nodes again and again and reaches no end.
You get the head of a linked list. Return true if following next links ever reaches a node already visited, and false otherwise.
The samples describe the list as its values plus pos, the position (from 0) of the node the last node links back to, with -1 for no cycle. Your function sees only the head.
Constraints
- The list has between 0 and nodes
- Follow-up: use extra memory
Sample 1 · Input
head = [3,2,0,-4], pos = 1
Output
true
Sample 2 · Input
head = [1,2], pos = 0
Output
true
Sample 3 · Input
head = [1], pos = -1
Output
false
The direct method is to walk the list and add each node to a set. If the walk reaches a node that is already in the set, the list has a cycle, and if it reaches null, the list has none. This takes time, and it also takes memory, one set entry per node. The follow-up asks for .
The fast and slow pointers of the previous section need only their two variables. Take the list 10 → 20 → 30 → 40 → 50 → 60 whose last node links back to 30, and move the pointers as before:
After four steps both pointers are on 50, and that can only happen in a list with a cycle. Without one, fast stays ahead of slow until it reaches the end, and the answer is false.
With a cycle, neither pointer reaches an end, and after enough steps both are on the cycle. From then on, count the links from fast forward to slow around the cycle. Each step moves fast two nodes and slow one, so this gap shrinks by exactly one link per step. At step 2 above it is two links (), at step 3 one link, and at step 4 none. Because the gap shrinks one link at a time, fast cannot jump over slow: the gap reaches 0, and the two pointers are on the same node.
def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseOn the first sample, has_cycle returns True.
This is the loop of middle_node with one comparison added. The comparison is between the nodes, not their values: slow is fast asks whether the two variables refer to the same node object. Two different nodes can hold equal values, and that says nothing about a cycle.
The comparison comes after the pointers move. Both start on the head, so a comparison placed before the move would be true on the first turn for any list of two or more nodes.
slow reaches the cycle after one step for each node before it. At that moment the gap from fast to slow is less than one lap, so it closes by the time slow has gone once around the cycle. The nodes before the cycle and one lap of it add up to , so the walk takes at most steps: time and extra memory.
Step through the walk
The widget runs the two pointers on the same list. Try linking the last node to a different node, or to none, to see a cycle of another length and a list without one. After the pointers meet, the widget goes on to a second walk, which the next section explains.
Find the node where the cycle begins
Once we know that a list has a cycle, we can ask where the cycle begins. The first node of the cycle that a walk from the head reaches is called the cycle's entry. In the list above the entry is 30.
You get the head of a linked list. Return the node where its cycle begins, or null if it has no cycle. The samples use pos as in Linked List Cycle, and you may not change the list.
Constraints
- The list has between 0 and nodes
- Follow-up: use extra memory
Sample 1 · Input
head = [3,2,0,-4], pos = 1
Output
tail connects to node index 1
Sample 2 · Input
head = [1,2], pos = 0
Output
tail connects to node index 0
Sample 3 · Input
head = [1], pos = -1
Output
no cycle
The set of visited nodes answers this as well, since the first node the walk finds already in the set is the entry, but it still uses memory. The method with two pointers is called Floyd's cycle detection, and for this question it adds a second walk:
- Move
slowandfastas before until they meet. - Put
slowback on the head and leavefastwhere it is. - Move both pointers one node per step. The node where they meet again is the entry.
On our list the pointers met on 50. The second walk starts with slow on 10 and fast on 50, moves them to 20 and 60, and then to 30 and 30, which is the entry.
10 → 20 → 30 → 40 → 50 → 60 with 60 linked back to 30. The first walk ends on 50, and the entry is 30.To see why the second walk ends on the entry, we name two lengths in the list. Let be the number of links from the head to the entry, and the number of nodes on the cycle. In the figure and .
Suppose the first walk took steps. Then slow followed links from the head to the meeting node, and fast followed . Following links from the head always leads to the same node, so the first links that fast followed also took it to the meeting node. Its other links therefore lead from the meeting node back to the meeting node. A walk can only come back to a node by going around the cycle, so those links are a whole number of laps, and is a multiple of . In the example , which is one lap.
Now follow the second walk for steps. slow starts on the head, so after links it is on the entry. fast starts on the meeting node, which is links from the head, so after more it is where links from the head lead. The first of those links reach the entry, and the other are whole laps, which end where they began. So after steps both pointers are on the entry. They cannot meet sooner, because until then slow is on the part of the list before the cycle and fast is on the cycle.
The code does not need to know . It stops the second walk when the two pointers are on the same node:
def detect_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return NoneOn the first sample, detect_cycle returns the node holding 2, at position 1.
The outer loop is has_cycle, and the inner loop is the second walk. The second walk takes steps, fewer than , so the two walks together still take time and extra memory.
Common linked-list mistakes
Changing a link before saving where it led.
- Where it breaks
- A reversal loop that points the link of
curatprevand then movescuralong that same link sendscurtoprev, which is null on the first turn. Reversing4 → 9 → 2returns the single node 4, and 9 and 2 are lost. - The fix
- Save the next node in
nxtfirst, and movecurontonxt.
Testing the link of
fastwithout testingfastitself.- Where it breaks
- A middle-finding loop that continues while the link of
fastis not null works on1 → 2 → 3and fails on1 → 2 → 3 → 4. Therefastgoes from 1 to 3 and then to null, and the next test asks null for its link. Null has none: Python raises anAttributeError, and in C++ reading through a null pointer is undefined behavior, which usually crashes the program. - The fix
- Test that
fastis not null first, and then that its link is not null.
Comparing values to detect a cycle.
- Where it breaks
- The list
5 → 1 → 1has no cycle. After one stepslowis on the first 1 andfastis on the second. Their values are equal, so a test on values reports a cycle. - The fix
- Compare the nodes themselves, as
has_cycledoes.
Recall How would you find the 3rd node from the end of a list in one pass?
Use two pointers that move at the same speed and keep a fixed gap of three nodes. Start fast and slow on the head and move fast three nodes forward. Then move both one node at a time until fast is null. slow is still three nodes behind, so it is on the third node from the end. No dummy is needed, because nothing is being unlinked.
Three more problems and the next lesson
Each of these three problems combines methods from above, and none has a worked solution here.
Judge problems
- Remove Nth Node From End of List(opens the judge in a new tab) ↗
This is the recall question above, followed by deleting the node it finds. Deleting is done from the node before, so put a dummy before the head, start both pointers on it, move
fastforward by the the problem gives, and then move both untilfastis on the last node. Stopping there, one step earlier than in the recall, leavesslowjust before the node to remove, and the dummy makes that work even when the node to remove is the head. - Reorder List(opens the judge in a new tab) ↗
The answer takes nodes from the front and the back of the list in turn, and a singly linked list cannot be walked backwards. Cut the list after the node that
middle_nodereturns, reverse the second half, and link the two halves together, one node from each in turn. - Find the Duplicate Number(opens the judge in a new tab) ↗
Read each value as a link: from index , go to index
nums[i]. Every value is between 1 and , so a walk from index 0 stays inside the array, and with only indices to visit it has to run into a cycle. No value is 0, so no index links to index 0, and index 0 lies before the cycle. The entry of the cycle is therefore reached from two different indices, the last index before the cycle and the last index on the cycle. Both hold the entry's index as their value, so that index is the repeated value.detect_cyclefinds it withnums[i]in place of a node's link.
Related chapters
- Data structure design →
An LRU (least recently used) cache keeps its entries in a doubly linked list and finds each node through a hash map, so looking a key up and moving its node to the front both take .
Further reading
- Sedgewick and Wayne, Algorithms, 4th edition1.3 Bags, Queues, and Stacks(opens in a new tab)
Its section on linked lists draws each basic operation (insert at the beginning, remove from the beginning, insert at the end, traversal) and then builds a stack and a queue out of nodes.
- MIT 6.006 lecture notes, Spring 2020Lecture 2: Data Structures(opens in a new tab)
The sequence interface implemented three ways, as a static array, a linked list and a dynamic array, with a cost table like the one above and the amortized analysis of appends.
- USACO Guide, SilverIntroduction to Functional Graphs(opens in a new tab)
Floyd's algorithm on graphs where every vertex has one outgoing edge, with a contest problem solved by the two walks.
- WikipediaCycle detection(opens in a new tab)
Floyd's tortoise and hare in terms of the tail length and cycle length, the second walk that finds the entry, and Brent's method, which finds the cycle length directly.
- OI Wiki, in Chinese链表 (Linked lists)(opens in a new tab)
Singly, doubly and circular lists side by side, with code for inserting and deleting nodes, and the XOR linked list that stores both links in one field.
- Pat MorinOpen Data Structures, Chapter 3: Linked Lists(opens in a new tab)
A singly linked list that keeps both its head and its last node, so that it works as a stack and as a queue, then a doubly linked list built around one dummy node, which removes the special cases at both ends. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.