Linked List

An array keeps items in fixed neighbouring slots, so inserting in the middle means shuffling everything along. A linked list solves that. Each item sits in a node that also stores a pointer to where the next item is. To insert or remove an item you just change a couple of pointers — the data itself never moves.

Think of a treasure hunt: each clue tells you where the next clue is hidden. You start at the first clue (the start pointer) and follow the trail until a clue says “this is the last one” (a null pointer). Re-routing the hunt is easy — you only rewrite which clue points where.

Since Python has no built-in pointer type, we simulate the list with two arrays: a data array holding the values and a pointer array holding, for each node, the index of the next node. We also keep a free list of unused nodes.

We store the list in two arrays of the same length. The data array holds the values. The pointer array holds, at the same index, the location of the next node. Two variables complete the picture: start (index of the first node) and free (index of the first unused node). Unused nodes are chained together exactly like the list — that chain is the free list.

MAX = 7
data  = [None] * MAX     # the values
nextp = [None] * MAX     # index of the next node
start = -1               # -1 = empty list
free  = 0                # first free node

def setup():
    global start, free
    start = -1
    free = 0
    for i in range(MAX - 1):
        nextp[i] = i + 1      # each free node links to the next
    nextp[MAX - 1] = -1       # last free node -> null

Here is a list of three marks — 60, 45, 88 — stored in the arrays. The start pointer says the first node is at index 2; from there you follow the pointer array.

Read the list by starting at index 2 (60), following nextp: 2 → 1 → 0 → null gives 60, 45, 88. The free list begins at index 3. Pointers: start = 2, free = 3.

Try the linked list yourself. Set MAX_SIZE, enter a value, and click Insert Front, Find, or Delete. Step through the pointer moves one at a time, or press Play to watch them run automatically. The free list starts pre-linked — every insert takes a node from it, every delete returns one to it.

1# Choose Insert, Find, or Delete to see the code highlighted here.

To find a value, set a current pointer to start and step along: if the current node's data matches, stop; otherwise move current to nextp[current]. When current becomes -1 you've run off the end without finding it.

def find(target):
    current = start
    while current != -1:          # until we run off the end
        if data[current] == target:
            return current        # found - give its index
        current = nextp[current]  # follow the pointer
    return -1                     # not found

To insert a value at the front: take the first free node, store the data there, make the new node point to the old start, then move start to the new node. The free pointer moves on to the next free node.

def insert_front(item):
    global start, free
    if free == -1:                 # no free nodes left
        print("List full")
    else:
        new = free                  # take a free node
        free = nextp[free]          # free list moves on
        data[new] = item            # store the data
        nextp[new] = start          # new node points to old start
        start = new                 # start now points to new node

We walk the list keeping track of the previous node as well as the current one. When we find the target, the previous node's pointer is set to skip over it. If the target is the very first node, we just move start instead. Finally we link the removed node onto the front of the free list so it can be reused.

def delete(target):
    global start, free
    current = start
    previous = -1
    while current != -1 and data[current] != target:
        previous = current
        current = nextp[current]
    if current == -1:
        return False            # not found
    if previous == -1:
        start = nextp[current]      # delete the first node
    else:
        nextp[previous] = nextp[current]   # bypass the node
    nextp[current] = free           # return node to free list
    free = current
    return True

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked Python solution.