Cambridge A-Level Computer Science – Algorithms: Abstract Data Types (ADT)
19.1 Algorithms – Understanding and Using Abstract Data Types (ADT)
What is an Abstract Data Type?
An Abstract Data Type (ADT) defines a data structure purely by its behaviour – the operations that can be performed on it and the mathematical properties of those operations. The implementation details (how the data is stored in memory) are hidden.
Key Characteristics of an ADT
Encapsulation – only the defined operations are visible to the user.
Specification – a formal description of each operation (pre‑conditions, post‑conditions, and complexity).
Implementation independence – the same ADT can be realised with different concrete structures (e.g., array vs. linked list).
Common ADTs in the A‑Level Syllabus
ADT
Typical Operations
Typical Implementations
Stack
push(x) – insert element on top
pop() – remove and return top element
top() – view top element without removing
isEmpty()
Array (fixed size) or singly linked list
Queue
enqueue(x) – insert at rear
dequeue() – remove and return front element
front()
isEmpty()
Circular array or doubly linked list
List
insert(i, x) – insert x at position i
delete(i) – remove element at position i
get(i) – retrieve element at i
size()
Dynamic array (e.g., Python list) or doubly linked list
Map (Associative Array)
put(k, v) – associate key k with value v
get(k) – retrieve value for key k
remove(k)
containsKey(k)
Hash table or binary search tree
Formal Specification of an ADT
When specifying an ADT we give:
Signature – name of the ADT and the types of its operations.
Pre‑conditions – what must be true before an operation is called.
Post‑conditions – the effect on the abstract state after the operation.
Complexity – usually expressed using Big‑O notation.
Below is pseudo‑code that respects the abstract specification while using a fixed‑size array.
CONST MAX = 100
TYPE StackArray
data: array[0..MAX‑1] of integer
topIndex: integer ← -1
PROCEDURE push(S: StackArray, x: integer)
IF S.topIndex = MAX‑1 THEN
ERROR "Stack overflow"
END IF
S.topIndex ← S.topIndex + 1
S.data[S.topIndex] ← x
END PROCEDURE
FUNCTION pop(S: StackArray) RETURNS integer
IF S.topIndex = -1 THEN
ERROR "Stack underflow"
END IF
x ← S.data[S.topIndex]
S.topIndex ← S.topIndex - 1
RETURN x
END FUNCTION
FUNCTION top(S: StackArray) RETURNS integer
IF S.topIndex = -1 THEN
ERROR "Stack empty"
END IF
RETURN S.data[S.topIndex]
END FUNCTION
FUNCTION isEmpty(S: StackArray) RETURNS boolean
RETURN S.topIndex = -1
END FUNCTION
Complexity Comparison – Array vs. Linked List Stack
Operation
Array Implementation
Linked‑List Implementation
push
\$O(1)\$ (amortised if dynamic resizing)
\$O(1)\$
pop
\$O(1)\$
\$O(1)\$
top
\$O(1)\$
\$O(1)\$
isEmpty
\$O(1)\$
\$O(1)\$
Design Exercise – Using an ADT in an Algorithm
Design an algorithm that checks whether a given string of parentheses is balanced. Use the Stack ADT.
Read the input string \$s\$ of length \$n\$.
Create an empty stack \$S\$.
For each character \$c\$ in \$s\$:
If \$c\$ is an opening bracket ‘(’, ‘[’, or ‘{’, push \$c\$ onto \$S\$.
If \$c\$ is a closing bracket, check:
If \$S\$ is empty, the string is unbalanced – stop.
Pop the top element \$t\$ and verify that \$t\$ matches \$c\$ (e.g., ‘(’ matches ‘)’).
After the loop, if \$S\$ is empty the string is balanced; otherwise it is not.
The algorithm’s time complexity is \$O(n)\$ because each character is processed once and each stack operation is \$O(1)\$. The space complexity is \$O(k)\$ where \$k\$ is the maximum nesting depth of brackets (worst‑case \$k = n\$).
Suggested diagram: Flowchart of the balanced‑parentheses algorithm showing the loop, stack operations, and decision points.
Key Take‑aways
An ADT describes *what* a data structure does, not *how* it does it.
Formal specifications help in reasoning about correctness and complexity.
Multiple concrete implementations can satisfy the same ADT; choose based on performance requirements.
When solving algorithmic problems, selecting the appropriate ADT simplifies design and analysis.