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)

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?