Linked lists

Nodes joined by links

• A linked list is a chain of nodes.
• Each node holds a piece of data and a link to the next node.
• The last node links to None, which marks the end.

A node is a small record

• We can store one node in a dictionary: {"data": ..., "next": ...}.
• "data" holds the value; "next" holds the next node (or None).
• The first node is called the head of the list.

second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])

Walk the list

• Start at the head and follow each "next" link.
• Stop when you reach None.
• This visiting of every node is called traversal.

head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
    print(node["data"])
    node = node["next"]

Why a linked list?

• You can insert or remove a node by changing links — no shifting of items.
• An array would have to move every item after the change.
• But a linked list has no index: to reach item 5 you must walk from the head.

In Cambridge pseudocode

• The exam stores nodes in an array; Next is the index of the next node, and NULL marks the end.

TYPE Node
    DECLARE Data : INTEGER
    DECLARE Next : INTEGER    // index of the next node, or NULL
ENDTYPE

current ← head
WHILE current <> NULL
    OUTPUT list[current].Data
    current ← list[current].Next
ENDWHILE

Common mistakes

• Never lose the head pointer, or the whole list is unreachable.
• The last node points to None.

Now you try

• A node is a dict {"data": ..., "next": ...}. Follow "next" to walk the chain.
• Press Check answer to test your code.