Linked Lists

Lesson 4 of 7 in Foundations · 35 min · Beginner

A chain of nodes, each holding the way to the next.

Introduction

A treasure hunt gives you a first clue, and every clue only tells you where the next one is hidden. How do you slip a new clue into the middle of the hunt without rewriting all the clues after it?

Clue 1 says "look under the red bench". Under the bench is clue 2: "check the oak tree". Under the oak is clue 3, and so on. Nobody holds the whole route. Each clue knows one thing: the next stop.

Now you want a new clue between clue 2 and clue 3. If the clues sat in a row of boxes, you would have to shift every later clue one box along. Here, only two notes change. What are they?

Lesson overview

This lesson will show you how to:

Explain why each node stores a value and a pointer to the next node.
Trace an insert in the middle by rewiring two next pointers.
Trace a delete by bypassing the node that should go.
Reverse a list in place by turning each arrow around.
Choose a linked list when you already hold the spot to change.

The picture

Linked list: 12 → 7 → 31 → 5 → null. Pointers: head at 12.

Mental model

Picture a train of carriages. Each carriage carries its cargo (the value) and has one coupling that hooks it to the carriage behind it, and the last carriage's coupling hooks to nothing.

You only hold the front carriage. To reach carriage 5 you walk through 1, 2, 3 and 4, and to add a carriage in the middle you unhook one coupling and hook in two.

A node knows only its value and who comes next, so changing a next link is changing the order.

Words to know

node: One box in the list: a value plus a next link.
head: The first node. It is the only one you hold on to, so if you lose it you lose the whole list.
next: The link inside a node that says which node comes after it.
null: "Nothing here." The last node's next is null, which marks the end of the list (None in Python, nullptr in C++).
dummy node: A throwaway node placed in front of the head so that the head stops being a special case.
in-place: Changing the links of the nodes you already have instead of building a new list, so no extra space is needed.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: The problem hands you a head (a ListNode) instead of an array.
Yes: You insert or delete in the middle a lot, and you already hold the spot.
Yes: It says in place, or O(1) extra space, on a list.
Yes: The job is rewiring the order: reverse, merge, splice or reorder.

Not this when

No: You need the k-th element fast: an array jumps there in O(1), a list has to walk k steps.
No: You need to look something up by value: a hash map finds it without walking.
No: The list may loop back on itself, or you need its middle: it is still a list, but the move is fast and slow pointers.

Which pattern fits?

Which pattern? 1 of 4
Given the head of a linked list, decide whether the list contains a cycle.
Which pattern? 2 of 4
A million numbers are stored, and you must read the one at position 1000, again and again, very quickly.
Which pattern? 3 of 4
An editor has an undo button that removes the most recent change first, then the one before it.
Which pattern? 4 of 4
Given the head of a singly linked list, reverse it in place and return the new head.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1prev = null, curr = head
2while curr is not null:
3nxt = curr.next (remember the way on)
4curr.next = prev (turn the arrow around)
5prev = curr, curr = nxt (slide forward)
6return prev (the new head)

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_list(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Time · O(n)Space · O(1)

Walking the list once touches every node once, so traversing, searching and reversing are O(n).
Once you stand on the right node, inserting after it or deleting the next one is O(1): a couple of link writes. Getting there is the O(n) part.
Before you overwrite curr.next, make sure something else still points at the rest of the list. Save it first, as nxt does in the reversal.
A dummy node in front of the head means deleting the head is the same code as deleting any other node, because there is always a prev.
Check for null before you read curr.next, and test an empty list, a single node and the tail.

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

You insert a new node after curr. Why do you set node.next = curr.next before curr.next = node?
Why does deleting a node from a singly linked list need the node before it?
How do reading the k-th element of a linked list and of an array compare?
In the reversal loop, what goes wrong if you flip curr.next = prev without saving nxt first?
What does a dummy node in front of the head buy you when you delete a node?

Question 1 of 5

You insert a new node after curr. Why do you set node.next = curr.next before curr.next = node?

It is faster to write the new node's link first.curr.next is the only link to the rest of the list, so overwriting it first would lose that rest.The order doesn't matter, because both writes give the same list.Python and Java require the new node's link to be written first.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

Solve Linked List Cycle (opens in a new tab) (LeetCode, easy)
Hint: A pointer that moves two nodes per step will eventually catch one that moves a single node per step, if (and only if) the list loops.
Solve Middle of the Linked List (opens in a new tab) (LeetCode, easy)
Hint: Move one pointer twice as fast as another. Where is the slow one when the fast one runs out of list?
Solve Palindrome Linked List (opens in a new tab) (LeetCode, easy)
Hint: You can't walk backwards, but you can reverse the second half in place and compare it with the first half.
Solve Intersection of Two Linked Lists (opens in a new tab) (LeetCode, easy)
Hint: If each pointer switches to the other list's head after reaching its own end, both walk the same total distance. Think about where they meet.
Solve Add Two Numbers (opens in a new tab) (LeetCode, medium)
Hint: Add digit by digit like on paper, carrying as you go, and build the answer behind a dummy node.
Solve Reorder List (opens in a new tab) (LeetCode, medium)
Hint: It combines three moves you know: find the middle, reverse the second half, then weave the two halves together.
Solve LRU Cache (opens in a new tab) (LeetCode, medium)
Hint: A hash map finds a node instantly, and a doubly linked list lets you pull it out and move it to the front in O(1).
Solve Reverse Nodes in k-Group (opens in a new tab) (LeetCode, hard)
Hint: Reverse one group of k with the same prev/curr/nxt loop, then reconnect it to the groups before and after.

Additional resources

Linked list (opens in a new tab) — Surveys singly, doubly and circular lists, with their trade-offs against arrays.
Doubly linked list (opens in a new tab) — Shows how back-links make removal easier, at the cost of extra pointers.
VisuAlgo: List (opens in a new tab) — Animated list operations you can pause, so each pointer change is easy to follow.