Arrays and searching 0/120

Lesson 8 of 9

Linked lists

Reverse a list by rewiring links in a safe order, merge and edit lists with a dummy head, and find middles and cycles with fast and slow pointers.

5,468 words · 25 min read

Part 1 of 10 Nodes and links

A sequence stored as nodes

A Python list keeps its items in consecutive slots of memory. Reading the item at position ii 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

105 inserts×106 items each=1011 items10^5 \text{ inserts} \times 10^6 \text{ items each} = 10^{11} \text{ items}

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 ii 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.

4head92null

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:

Sign up to run
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.