Linked lists

Nodes and pointers, the free list, and traversing, inserting and deleting: a route of waypoints.

A3.4Data structuresA level25 min

To add a waypoint in the middle of a route stored in an array, you would have to move every later waypoint along one place to make room. A linked list avoids that: each item says where the next one is, so adding or removing an item means changing a pointer or two, however long the list. In this lesson BugBot's route is a linked list, and you reroute it round a closed waypoint.

Nodes and pointers

A linked list is made of nodes. Each node holds some data and a pointer to the next node. The list also has a start pointer (sometimes called the head) to the first node, and the last node's pointer is null, meaning "no next node".

The nodes do not have to sit next to each other in memory, or in order. The order of the list is the order of the pointers. That makes a linked list a dynamic data structure: a node can be created whenever one is needed.

In Python a node can be a record with two fields, and None is the null pointer:

from dataclasses import dataclass

@dataclass
class Node:
    data: str
    next: object = None           # None is Python's null pointer

a, b, c = Node("dock"), Node("ramp"), Node("gate")
a.next = b
b.next = c
start = a

cur = start                       # traverse: follow the pointers from the start
while cur is not None:
    print(cur.data)
    cur = cur.next

Run this in the simulator

A linked list in arrays

Exam questions usually store a linked list in arrays: one array for the data, one for the pointers, where a pointer is simply the index of the next node, and -1 stands for null. Unused nodes are kept in a second linked list, the free list, with its own pointer free.

This list holds the marker ids 5, 17 and 23 in order. The start pointer is 1, so the list begins at index 1, not index 0.

start = 1, free = 3. Following the pointers: index 1 (5) → index 0 (17) → index 2 (23) → -1, the end. The free list is index 3 → index 4 → -1.

Traversing

To traverse a linked list, start at the start pointer and follow each node's pointer until you reach null:

cur = start
while cur != -1
    print(data[cur])
    cur = next[cur]
endwhile

A traversal is the only way to reach the fifth item: there is no direct access by position, so searching a linked list is always a linear search, even if the data is in order.

Inserting

To insert 20 in order:

1. Check the free list is not empty. Take the first free node: new = free, then free = next[free].
2. Store the data: data[new] = 20.
3. Traverse to find where it goes, keeping two pointers: prev, the node before, and cur, the first node whose data is larger (here prev is index 0, holding 17, and cur is index 2, holding 23).
4. Point the new node at cur: next[new] = cur.
5. Point prev at the new node: next[prev] = new. If there is no prev, the new node is first, so start = new.

Steps 4 and 5 must be in that order. Change prev's pointer first and you lose the only record of where the rest of the list is.

Deleting

To delete 5:

1. Traverse to find the node (cur) and the node before it (prev).
2. Bypass it: next[prev] = next[cur], or if it is the first node, start = next[cur].
3. Return it to the free list: next[cur] = free, then free = cur.

The data is not wiped. The node simply is no longer reachable from start, and it is ready to be reused.

data = [17, 5, 23, None, None]
nxt  = [2,  0, -1, 4,    -1]
start = 1
free = 3

def show():
    items = []
    cur = start
    while cur != -1:
        items.append(data[cur])
        cur = nxt[cur]
    print("list:", items, " start =", start, " free =", free)

def insert_in_order(value):
    global start, free
    if free == -1:
        print("no free space")
        return
    new = free                     # take the first free node
    free = nxt[free]
    data[new] = value
    prev, cur = -1, start
    while cur != -1 and data[cur] < value:
        prev, cur = cur, nxt[cur]
    nxt[new] = cur                 # the new node points at the rest of the list first
    if prev == -1:
        start = new                # it goes at the front
    else:
        nxt[prev] = new

def delete(value):
    global start, free
    prev, cur = -1, start
    while cur != -1 and data[cur] != value:
        prev, cur = cur, nxt[cur]
    if cur == -1:
        print(value, "is not in the list")
        return
    if prev == -1:
        start = nxt[cur]
    else:
        nxt[prev] = nxt[cur]
    nxt[cur] = free                # the freed node goes on the front of the free list
    free = cur

show()
insert_in_order(20)
show()
delete(5)
show()
print("data:", data)
print("next:", nxt)

Run this in the simulator

After both operations the arrays hold data = [17, 5, 23, 20, None] and next = [3, 4, -1, 2, -1], with start = 0 and free = 1. The 5 is still in data[1], but index 1 is now the head of the free list.

Arrays or linked lists?

Linked lists are used to build other structures: a stack or queue that never fills, the chains in a hash table (lesson A3.5), adjacency lists for graphs (module A4), and the free memory lists an operating system keeps.

Task: the linked route

BugBot's route is a linked list stored in the arrays names, xs, ys and nxt (coordinates in cm from where the robot starts, -1 is null), with start and free pointers. At the moment the route is A → B → E → C, but waypoint E is closed. Change only pointers and array elements; do not use the list methods insert, remove, pop or del.

1. Write delete(name): unlink the node called name and put its slot on the front of the free list.
2. Write insert_after(before, name, x, y): take the slot at the front of the free list, store name, x and y in it, link it in straight after the node called before, and return the slot's index.
3. Delete "E", then insert "D" at (40, 60) after "B", and print D stored at index <index>.
4. Traverse the list and print the names in order, separated by single spaces: route: A B D C.
5. Traverse again, calling go_to(xs[i], ys[i]) for each node, so the robot drives the route without passing through E.

Both functions change start or free, so declare them global inside the functions.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def go_to(x, y):
    """Drive to (x, y) cm from the start: across first, then up or down."""
    px, py = position()
    dx, dy = x - px, y - py
    if dx > 1:
        right(50, distance=dx)
    elif dx < -1:
        left(50, distance=-dx)
    if dy > 1:
        forward(50, distance=dy)
    elif dy < -1:
        backward(50, distance=-dy)

# the route as a linked list held in arrays; -1 is the null pointer
names = ["C", "B", "A", "E", "", ""]
xs    = [0,   40,  0,   20,  0,  0]
ys    = [60,  20,  20,  40,  0,  0]
nxt   = [-1,  3,   1,   0,   5,  -1]
start = 2
free = 4

def delete(name):
    pass

def insert_after(before, name, x, y):
    pass

Challenges

1. Draw the four arrays and both pointers after your program has run. Check them by printing the arrays.
2. A doubly linked list also stores a pointer to the previous node. What does that make easier, and what does it cost?
3. What should insert_after do if the free list is empty? And if there is no node called before?