Module 06: Core data structures

An abstract data type specifies operations and behaviour; a data structure implements them. A stack promises last-in-first-out removal regardless of whether it uses an array or links. Separate the operation contract from its cost. Choose around workload: frequent indexed reads, front removals, key lookups and ordered scans favour different structures. An implementation should also specify empty behaviour, duplicate policy and ownership of mutable values.

An array places elements in indexed slots, enabling constant-time indexed access in the usual RAM model. A dynamic array grows its backing storage when capacity runs out. A single append may copy n entries, yet geometrically increasing capacity gives amortised O(1) append: across many appends, total copies grow only linearly. Inserting at the front shifts entries and is O(n). Python lists are dynamic arrays of references, not packed arbitrary Python objects. Locality often makes sequential array scans practical despite abstractly similar costs elsewhere.

A linked node stores a value and a reference to the next node. Prepending only changes a few references. Indexed access requires following links, so reaching position i costs O(i). Inserting after an already-known node is O(1), but finding that node may cost O(n). Deleting requires access to the predecessor in a singly linked list. Links consume extra memory and can reduce locality. The stack lab makes these references visible rather than hiding the implementation inside a built-in list.

Stacks remove the newest item first; queues remove the oldest. Undo history uses a stack; waiting tasks often use a queue. A linked stack pushes and pops at its head in O(1). A deque supports efficient operations at both ends and avoids Python list pop(0), which shifts remaining references. Empty removal needs a defined result or exception. Later, recursion uses a call stack and breadth-first graph search uses a queue; the behavioural order determines the algorithm.

A hash function maps keys to bucket indices. Different keys may collide, so a table must compare original keys within a chain or use another collision strategy. Updating an existing key should replace its value rather than add a duplicate. Expected O(1) lookup depends on appropriate hashing and controlled load; worst-case chains can be O(n). The load factor is entries/buckets. Resize and rehash when necessary. Our byte-sum hash is intentionally poor: anagrams collide. Python dictionaries use a much more sophisticated implementation; do not substitute this toy for them.

Download each script and run it in a terminal with Python 3.11 or later: python m06_structures.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

Follow head and next references. Compare the removal order for identical inputs.

Download m06_structures.py

"""A linked stack and a FIFO queue with explicit empty behaviour."""
from collections import deque
class Node:
    def __init__(self, value, next_node=None):
        self.value, self.next = value, next_node
class Stack:
    def __init__(self):
        self.head = None
    def push(self, value):
        self.head = Node(value, self.head)
    def pop(self):
        if self.head is None:
            raise IndexError("empty stack")
        node = self.head
        self.head = node.next
        return node.value

stack, queue = Stack(), deque()
for book in ["Dune", "Foundation", "Solaris"]:
    stack.push(book); queue.append(book)
print("stack:", [stack.pop() for _ in range(3)])
print("queue:", [queue.popleft() for _ in range(3)])
try:
    stack.pop()
except IndexError:
    print("empty pop rejected")

stack: ['Solaris', 'Foundation', 'Dune']
queue: ['Dune', 'Foundation', 'Solaris']
empty pop rejected

1. Add a peek operation without removal.
2. Test one push/pop and an empty queue.
3. Draw the chain after two pushes.

ab and ba share a bucket but remain different keys. The update changes ab's value without growing its chain.

Download m06_hash.py

"""A deliberately small chained table makes collisions visible."""
class Table:
    def __init__(self, buckets=4):
        if buckets < 1:
            raise ValueError("positive bucket count required")
        self.buckets = [[] for _ in range(buckets)]
    def slot(self, key):
        return sum(key.encode("utf-8")) % len(self.buckets)
    def put(self, key, value):
        chain = self.buckets[self.slot(key)]
        for i, (stored, _) in enumerate(chain):
            if stored == key:
                chain[i] = (key, value); return
        chain.append((key, value))
    def get(self, key):
        for stored, value in self.buckets[self.slot(key)]:
            if stored == key:
                return value
        raise KeyError(key)

table = Table()
for key, value in [("ab", 1), ("ba", 2), ("c", 3), ("ab", 4)]:
    table.put(key, value)
print("chains:", table.buckets)
assert table.get("ab") == 4 and table.get("ba") == 2
try:
    table.get("missing")
except KeyError:
    print("missing key rejected")

chains: [[], [], [], [('ab', 4), ('ba', 2), ('c', 3)]]
missing key rejected

1. Use one bucket and count scanned entries.
2. Add delete with an explicit missing-key rule.
3. Double bucket count and reinsert all entries.

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• Python deque — Compare endpoint operations with list front removal.

Explain a workload where each structure is appropriate. Trace the stack's references and a collision update. Module 07 uses stacks and queues to traverse recursive structures.