Unit 22: Linked Lists

Chains of boxes.

Unit 22 of 31 in Python for kids. Its 5 lessons are Nodes and Chains, Walking the Chain, Adding Links, Finding and Removing and Chain Master — below is everything each one explains, and a question or two from it to try.

Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.

This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.

⛓️ Nodes and Chains

A box that knows what comes next

Instead of a row of boxes, a linked list is a chain. Each node holds a value and a pointer to the next node. The last one points at None.

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

first = Node("a")
second = Node("b")
first.next = second

print(first.value)
print(first.next.value)
print(first.next.next)

It prints

a
b
None

The nodes are not in a row

This is the real difference. Array boxes sit side by side, so pets[500] is a sum. Chain nodes can be anywhere in memory, so getting to the 500th means following 500 pointers.

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

a = Node(1)
a.next = Node(2)
a.next.next = Node(3)
print(a.next.next.value)

It prints

Try it yourself

How do you know you have reached the end of a chain?

You count the nodes first
The next pointer is None
The value is empty
It loops back to the start

So which is faster at finding the 100th item?

The linked list
The array — it works out the position, instead of following 100 pointers
They are the same
Neither can do it

Answer them in the app

🚶‍♀️ Walking the Chain

One node at a time

Keep a marker on the current node, print it, then move the marker on. Stop when the marker reaches None. This pattern is the whole of linked lists.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node("a")
head.next = Node("b")
head.next.next = Node("c")

current = head
while current is not None:
    print(current.value)
    current = current.next

It prints

a
b
c

Counting and totalling

Once you can walk a chain you can do anything to it — count it, add it up, find the biggest.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node(4)
head.next = Node(6)

count = 0
total = 0
current = head
while current:
    count = count + 1
    total = total + current.value
    current = current.next
print(count, total)

It prints

2 10

Keeping hold of the head

Never move head itself — once you have lost the first node, the whole chain is gone and nothing can find it again. Always walk with a separate marker.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node(1)
head.next = Node(2)

current = head
while current:
    current = current.next

print(head.value)

It prints

Try it yourself

What does current = current.next do?

Deletes the current node
Moves the marker along to the following node
Adds a node
Goes back one

Answer it in the app

🔗 Adding Links

Adding at the front is instant

Here is where the chain wins. Point the new node at the old first one, and call it the new head — no shuffling, however long the chain is.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node("b")

new = Node("a")
new.next = head
head = new

current = head
while current:
    print(current.value)
    current = current.next

It prints

a
b

Adding at the end means walking there

To add at the end you must first find the end — so this one is slow, exactly the opposite way round from an array.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node("a")

current = head
while current.next:
    current = current.next
current.next = Node("b")

print(head.value, head.next.value)

It prints

a b

Squeezing one into the middle

Point the new node at whatever came next, *then* point the node before it at the new one. Do it the other way round and you lose the rest of the chain.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node("a")
head.next = Node("c")

middle = Node("b")
middle.next = head.next
head.next = middle

current = head
while current:
    print(current.value)
    current = current.next

It prints

a
b
c

Try it yourself

Why is adding at the front of a chain faster than at the front of an array?

It is not
Nothing else has to move — only one pointer changes
Chains are shorter
Arrays cannot do it

Answer it in the app

✂️ Finding and Removing

Searching means walking

There is no shortcut — you look at each node in turn until you find it or run out of chain.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node(1)
head.next = Node(2)

def contains(head, wanted):
    current = head
    while current:
        if current.value == wanted:
            return True
        current = current.next
    return False

print(contains(head, 2))
print(contains(head, 9))

It prints

True
False

Removing means skipping over

You never really delete a node — you point the one before it at the one after, so nothing leads to it any more.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

head = Node("a")
head.next = Node("b")
head.next.next = Node("c")

head.next = head.next.next

current = head
while current:
    print(current.value)
    current = current.next

It prints

a
c

Try it yourself

To remove a node you must know…

Only the node itself
The node before it, so you can point it past
The whole chain
The last node

What does this print?

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

h = Node(1)
h.next = Node(2)
h.next.next = Node(3)
h.next = h.next.next

n = 0
c = h
while c:
    n = n + 1
    c = c.next
print(n)

Answer them in the app

🏆 Chain Master

Try it yourself

What does this print?

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

a = Node(1)
b = Node(2)
a.next = b
b.next = a.next
print(b.next.value)

Answer it in the app