Show understanding that an ADT is a collection of data and a set of operations on those data

10.4 Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a mathematical description of a collection of values together with the operations that can be performed on that collection. The description tells what the data are and what each operation does, but it does not prescribe how the operations are implemented.

Key ideas

  • Data set – the set of values that may be stored (e.g. a sequence of integers, a set of unique keys, etc.).

  • Operations – the functions or methods that manipulate the data (e.g. push, pop, add, remove).

  • Specification vs. implementation – the ADT specification is independent of any particular data structure (array, linked list, tree, …). Different concrete implementations can satisfy the same specification.

Why ADTs are used in programme design (Cambridge AO1–AO3)

  • Encapsulation – the internal representation can be changed without affecting the rest of the program.

  • Interchangeability – any implementation that meets the specification can replace another, supporting modular development and reuse.

  • Testing & correctness – the ADT can be unit‑tested in isolation; behaviour is defined by pre‑conditions, post‑conditions and invariants.

  • Design tools

    • Structure charts – ADTs appear as modules (boxes) that hide implementation details.

    • State‑transition diagrams – states such as empty, non‑empty and the transitions caused by operations are visualised.

Formal description of an ADT

For each ADT we give:

  1. Signature – the name of each operation, its parameters and return type.

  2. Pre‑condition – what must be true before the operation is called.

  3. Post‑condition – how the ADT’s state changes and what value (if any) is returned.

  4. Invariant – a property that is true for the ADT after every operation (e.g. a Set never contains duplicate elements).

Common ADTs (Cambridge examples)

ADTOperations (signature)Behaviour (informal description)Typical error condition
Stack

push(value: T) → void

pop() → T

peek() → T

isEmpty() → boolean

Last‑In‑First‑Out. push adds an element to the top; pop removes and returns the top element; peek returns the top element without removing it.Under‑flow – calling pop or peek when isEmpty() = true.
Queue

enqueue(value: T) → void

dequeue() → T

front() → T

isEmpty() → boolean

First‑In‑First‑Out. Elements are added at the rear and removed from the front.Under‑flow – calling dequeue or front on an empty queue.
List (array‑based or linked)

insert(index: int, value: T) → void

remove(index: int) → T

get(index: int) → T

size() → int

Ordered collection with random indexed access.Index‑out‑of‑range (negative or ≥ size()).
Set

add(value: T) → void

remove(value: T) → void

contains(value: T) → boolean

size() → int

Unordered collection of unique elements.None – adding a duplicate leaves the set unchanged (invariant: no duplicates).
Map (Dictionary)

put(key: K, value: V) → void

get(key: K) → V

remove(key: K) → V

containsKey(key: K) → boolean

Associates each unique key with a value.Key‑not‑found – calling get or remove with a key that is not present.

Mathematical description (example: Stack)

Let S be the current stack state, represented as an ordered sequence [s₁, s₂, …, sₙ] where sₙ is the top element. For a value v:

  • push: push(S, v) = [s₁, …, sₙ, v]

  • pop: Pre‑condition: n ≥ 1.

    pop(S) = (v, S') where v = sₙ and S' = [s₁, …, sₙ₋₁].

  • peek: Pre‑condition: n ≥ 1.

    peek(S) = sₙ

  • isEmpty: isEmpty(S) = (n = 0)

Pseudocode example – Stack implemented with an array

TYPE Stack
ARRAY data[0..MAX-1] OF INTEGER
INTEGER top ← -1          // -1 indicates an empty stack
END TYPE
FUNCTION push(s: REF Stack, v: INTEGER) → VOID
IF s.top = MAX-1 THEN
ERROR "Stack overflow"
ELSE
s.top ← s.top + 1
s.data[s.top] ← v
END IF
END FUNCTION
FUNCTION pop(s: REF Stack) → INTEGER
IF s.top = -1 THEN
ERROR "Stack under‑flow"
END IF
v ← s.data[s.top]
s.top ← s.top - 1
RETURN v
END FUNCTION
FUNCTION peek(s: REF Stack) → INTEGER
IF s.top = -1 THEN
ERROR "Stack under‑flow"
END IF
RETURN s.data[s.top]
END FUNCTION
FUNCTION isEmpty(s: REF Stack) → BOOLEAN
RETURN s.top = -1
END FUNCTION

Link to the Cambridge International AS & A Level Computer Science syllabus

  • Topic 10.4 – Abstract data types requires students to show understanding that an ADT is a collection of data and a set of operations on those data (assessment objective AO1).

  • The note above covers:

    • Definition of an ADT (data set + operations).

    • Separation of specification and implementation (AO2 – analysing solutions).

    • Formal signatures, pre‑/post‑conditions and invariants (AO3 – evaluating solutions).

    • Examples of the five ADTs listed in the syllabus (Stack, Queue, List, Set, Map).

    • Mathematical notation and a concrete pseudocode implementation to illustrate how a specification can be realised.

Summary checklist for learners

  • Can I state, in my own words, what an ADT is?

  • Do I know the five ADTs required by the syllabus and their typical operations?

  • Can I write the signature, pre‑condition and post‑condition for each operation?

  • Do I understand why the internal representation can be changed without breaking client code?

  • Am I able to sketch a simple state‑transition diagram for an ADT (e.g. empty ↔ non‑empty for a Stack)?

  • Can I implement one ADT in pseudocode and explain how it satisfies the specification?