Abstract Data Types (ADTs)

AQA 4.2.4 — Abstract Data Types

Retrieval: the previous lesson's arrays are a concrete structure - you access elements directly by index. This lesson introduces a different idea: describing a structure by what it can do, before deciding how to build it.

An Abstract Data Type (ADT) is defined by what operations it supports, not by how those operations are implemented. This separation — interface vs implementation — is a recurring theme across the whole specification (it reappears formally in Theory of Computation, Sequence 14).

A stack ADT, for example, is defined entirely by its interface: push, pop, peek, is_empty. You could implement it using a Python list, a linked list, or an array with a pointer — callers of the stack don't need to know or care which.

# Same push/pop/is_empty interface, two different implementations underneath.

# Implementation 1: a plain Python list, used directly with append()/pop()
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())   # "b"

# Implementation 2: wrapped in a class, hiding the underlying list entirely
class Stack:
    def __init__(self):
        self._items = []          # the implementation detail callers don't need to know

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

s = Stack()
s.push("a")
s.push("b")
print(s.pop())   # "b" - the caller only ever used push/pop/is_empty

Both give identical behaviour to any code that uses push/pop/is_empty — that's the point of an ADT: the interface is fixed, the implementation is free to change.

ADTs on this course

Common mistake

Don't confuse an ADT with its Python implementation. "A stack is a Python list" is imprecise — a Python list can implement a stack (by only ever using append/pop from one end), but the list itself supports far more operations (indexing anywhere, inserting in the middle) than the stack ADT's interface allows. The ADT is the restricted interface, not the underlying tool.

Why this distinction matters for the NEA

AQA's NEA marking criteria (Table 1) explicitly credit the use of ADTs like stacks, queues, hash tables and trees as evidence of higher-level technical skill (Group A/B) — precisely because choosing and correctly using the right ADT for a problem is itself a demonstration of computational thinking, separate from just "getting code to work".

Reflection

A browser's "back" button and a printer's job queue both need to store a sequence of items. Which ADT suits each, and why are they different?