Learn
B4.1.1 | ABSTRACT DATA TYPES (HL ONLY)
01 | DESCRIBE THE BEHAVIOUR BEFORE THE STORAGE
A text editor needs an undo history. When you undo an action, you expect the most recent saved action to be returned first. You do not normally care whether the history is stored in a resizable array or connected node objects, provided the expected behaviour is preserved.
An abstract data type, or ADT, describes a collection of possible values and the operations available on them, including what those operations mean. It gives a high-level description of a structure without fixing every storage detail.
For an undo history, a stack ADT is a natural starting point. The essential rule is last in, first out. The implementation is the code and storage arrangement chosen to provide that rule.
02 | UNPACK THE WORDS ABSTRACT DATA TYPE
| Word | Meaning here |
|---|---|
| Abstract | Focus on essential logical behaviour while leaving representation details out |
| Data | Specify what values or collections the model represents |
| Type | Define permitted operations and their meaning for those values |
Abstract does not mean incomplete or imprecise. A stack can have an exact rule about what pop returns without specifying an array index or node field. The logical description can be precise even while the representation remains open.
A useful ADT description tells a programmer how to use the structure correctly and gives an implementer a target to satisfy.
03 | THREE LAYERS TO KEEP SEPARATE
CALLER
The editor asks to push an action or pop the latest saved action.
ADT CONTRACT
The stack promises LIFO ordering, defined operations and an empty-stack policy.
IMPLEMENTATION
A list-based or linked representation carries out those operations.
The caller is the code using the structure. The contract describes observable behaviour. The implementation supplies the machinery. Keeping these layers separate lets you change the machinery without rewriting every caller.
For example, an editor should not need to know that one stack stores its top at the final list position. It should use pop rather than reach into the list and delete an arbitrary element.
04 | AN ADT NEEDS MORE THAN OPERATION NAMES
A method named remove tells us very little by itself. Which value does it remove? Does it return that value? What happens when the structure is empty? A high-level description must explain the operation semantics, meaning its effect and result.
| Contract part | Stack example |
|---|---|
| Possible state | A finite ordered sequence of stored values |
| Construction | A new stack starts empty |
| push(value) | Add value at the top |
| pop() | Remove and return the top value |
| peek() | Return the top value without removing it |
| Invalid case | Specify what pop and peek do when empty |
The contract can also specify permitted element types, capacity limits and relevant performance requirements. Do not assume these policies from a familiar method name.
05 | STACK: DEFINE A LOGICAL STATE
For this lesson, write the stack’s logical sequence from bottom to top. Starting empty, push Draft, then push Photo. The sequence is now [Draft, Photo], with Photo at the top. A pop must return Photo and leave [Draft].
The brackets here describe an ordered logical sequence. They do not require every stack implementation to use a Python list. The same logical state can be represented using linked nodes.
Our examples allow repeated values and have no fixed application capacity. Real memory remains finite. pop and peek on an empty stack raise an exception, while push returns no useful value.
06 | TRACE THE RULE BEFORE WRITING CODE
| Operation | Returned result | Logical state, bottom to top |
|---|---|---|
| Create | New empty stack | [] |
| push("Draft") | No useful result | [Draft] |
| push("Photo") | No useful result | [Draft, Photo] |
| peek() | Photo | [Draft, Photo] |
| pop() | Photo | [Draft] |
| pop() | Draft | [] |
| pop() | Empty-stack exception | [] |
peek and pop return the same top value when called on the same non-empty state, but only pop removes it. An invalid empty pop must not invent an ordinary data value or corrupt the structure.
If None or null is a permitted stored value, returning it for an empty stack could be ambiguous. An exception or an explicitly tagged result can make the distinction clear. Our Python classes use IndexError.
07 | PRECONDITIONS, POSTCONDITIONS AND INVARIANTS
| Term | Meaning | Example |
|---|---|---|
| Precondition | A condition required for a normal successful operation | The stack is non-empty for a successful pop |
| Postcondition | What must be true after an operation completes as specified | pop removes and returns the old top |
| Invariant | A condition maintained by valid states and operations | size equals the number of stored elements |
A checked implementation can reject a failed precondition with a defined exception. The normal pop postcondition does not apply to that rejected request, but the specified failure behaviour does.
These rules are useful for testing. If peek changes size, or pop returns the oldest value instead of the newest, the implementation violates the contract even if the code runs without a syntax error.
08 | FIRST IMPLEMENTATION: TOP AT THE END OF A LIST
class ListStack:
def __init__(self):
self._items = []
def push(self, value):
self._items.append(value)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._items[-1]
def is_empty(self):
return len(self._items) == 0
def size(self):
return len(self._items)
ListStack stores its values in a private-by-convention _items list. push appends at the end, and pop removes from that same end. The end therefore represents the top. peek uses the final position without removing it.
The checks make the empty-stack policy explicit. size and is_empty inspect the representation through controlled operations. The class exposes stack behaviour instead of offering every possible list operation.
This implementation uses Python’s resizable list. A different implementation could use a fixed array and an explicit top index, but would need to define what happens when capacity is reached.
09 | SECOND IMPLEMENTATION: TOP AT THE FIRST NODE
class _Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
class LinkedStack:
def __init__(self):
self._top = None
self._count = 0
def push(self, value):
self._top = _Node(value, self._top)
self._count += 1
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
value = self._top.value
self._top = self._top.next
self._count -= 1
return value
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._top.value
def is_empty(self):
return self._count == 0
def size(self):
return self._count
A node is a small object holding a value and a reference to the next node. _top identifies the first node. push creates a node pointing to the previous top; pop moves _top to the next node and returns the old top value.
None marks the absence of a next node or an empty top reference. It is a link marker here, not a separate stack item. _count records size and must stay consistent with the number of nodes.
The node details belong to this implementation. The next lessons investigate linked lists in depth; for now, notice that the public stack operations match ListStack even though the storage arrangement differs.
10 | TWO REPRESENTATIONS, ONE LOGICAL RESULT
| Aspect | ListStack | LinkedStack |
|---|---|---|
| Logical state | Draft at bottom; Photo at top | Draft at bottom; Photo at top |
| Top representation | Final list position | First linked node |
| push implementation | Append a value | Link a new first node |
| pop implementation | Remove final list item | Move top to the next node |
| Public promise | LIFO, defined operations and empty error | The same LIFO contract |
The linked representation visits the top before the bottom when you follow its links, while the list display runs bottom to top. Different internal display orders do not imply different ADT behaviour.
What matters to the caller is the sequence of results and permitted state changes, not whether the two internal pictures look identical.
11 | STEP THROUGH BOTH IMPLEMENTATIONS
The same actions run on two separate stacks. Predict each returned value and the next logical state. The table contrasts list storage from bottom to top with linked nodes from top to bottom. The trace data is generated by executing the Python classes.
12 | ONE CALLER CAN USE EITHER STACK
Place the two preceding stack implementations in the same Python file, then add this caller and click Run. The function needs only the common operations, not the concrete storage fields.
def use_stack(stack):
stack.push("Draft")
stack.push("Photo")
print(stack.peek())
print(stack.pop())
print(stack.pop())
print(stack.is_empty())
use_stack(ListStack())
use_stack(LinkedStack())
Each call prints Photo, Photo, Draft and True on separate lines. The first Photo comes from peek and leaves the item in place, so the following pop returns Photo again. The same output repeats for the second implementation.
This demonstrates representation independence for the stated contract. The implementation changes, but the caller’s required observations stay the same.
13 | JAVA: EXPRESS THE OPERATIONS WITH AN INTERFACE
import java.util.ArrayList;
interface StackADT<T> {
void push(T value);
T pop();
T peek();
boolean isEmpty();
int size();
}
class ArrayListStack<T> implements StackADT<T> {
private final ArrayList<T> items = new ArrayList<>();
public void push(T value) {
items.add(value);
}
public T pop() {
if (isEmpty()) throw new IllegalStateException("Stack is empty");
return items.remove(items.size() - 1);
}
public T peek() {
if (isEmpty()) throw new IllegalStateException("Stack is empty");
return items.get(items.size() - 1);
}
public boolean isEmpty() {
return items.isEmpty();
}
public int size() {
return items.size();
}
}
public class ADTExample {
public static void useStack(StackADT<String> stack) {
stack.push("Draft");
stack.push("Photo");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
public static void main(String[] args) {
useStack(new ArrayListStack<String>());
}
}
Save this as ADTExample.java and run main. StackADT<T> declares operations for a generic element type T. The example caller uses StackADT<String>, while ArrayListStack supplies a concrete representation. The output is Photo, Photo, Draft and true.
Java checks method declarations and types, but the interface alone cannot prove LIFO behaviour. A class could implement all method names and still remove the wrong item. The contract and tests establish the intended semantics.
The Java empty error here is IllegalStateException; the Python versions use IndexError. These are language-specific realisations of the same stated empty-rejection policy, rather than identical exception classes.
14 | ADT DOES NOT MEAN ABSTRACT CLASS
An ADT is a logical specification of values and operations. An abstract class is a particular OOP language mechanism for defining shared and required behaviour. They are related ideas, but they are not the same term.
You can implement an ADT with a concrete class, a suitable module or other language mechanisms. A Java interface or Python abstract base class can express some of its operation requirements, but neither replaces the behavioural description.
For example, the Python stack classes above use no @abstractmethod. They can still implement the same stack ADT because they provide the agreed operations and semantics.
15 | QUEUE: A DIFFERENT CONTRACT
| Operation sequence | Stack result | FIFO queue result |
|---|---|---|
| Add A, then B, then C; remove one | C | A |
| Inspect next value after that removal | B | B |
| Ordering rule | Last in, first out | First in, first out |
A FIFO queue adds at the rear and removes at the front. It suits a printer waiting list when the requirement is to serve the earliest waiting job first. A stack suits most-recent-first saved actions.
Both can be implemented with arrays or linked nodes, but they are different ADTs because their ordering semantics differ. Choosing the same storage technology does not make their contracts identical.
16 | LIST: POSITION IS PART OF THE MODEL
A list ADT represents a sequence of elements with meaningful positions. Typical operations include accessing an element at a position, inserting at a position, replacing a value, removing an element and obtaining the size. An exact specification must state index conventions and invalid-position behaviour.
A list permits duplicates and may be implemented with a resizable array or linked nodes. Python list is the name of a particular built-in implementation, whereas list ADT is the more general logical concept.
A stack can use a list implementation internally while exposing a narrower interface. If callers freely remove arbitrary middle items, they are no longer using only the stack contract.
17 | SET: MEMBERSHIP WITHOUT DUPLICATES
A set ADT represents distinct elements. Its essential meaning is membership, not numbered position or repeated copies. Adding an existing element does not add a second logical occurrence. Typical operations include contains, add, remove, union, intersection and difference.
| Logical operation | Result |
|---|---|
| Start with {A, B}; add A | {A, B} |
| Union of {A, B} and {B, C} | {A, B, C} |
| Intersection of those sets | {B} |
Unordered means the abstract contract does not promise a particular element sequence. It does not mean an implementation must randomise every display. The later set lessons explore operations and implementation choices more fully.
18 | MAP: ASSOCIATE KEYS WITH VALUES
A map ADT associates each distinct key with a value. You could map student IDs to attendance counts. Typical operations insert or update a mapping, look up a value by key, remove a key and test whether a key is present.
A common map contract replaces the previous value when an existing key is updated. Different keys may map to equal values. Missing-key behaviour must also be specified: exception, optional result or another documented policy.
A hash table or a suitable search-tree structure can implement mapping behaviour. A map is the logical association contract; hashing and tree links are representation choices.
19 | CHOOSE FROM THE REQUIRED BEHAVIOUR
| Requirement | Suitable ADT | Reason |
|---|---|---|
| Most recent saved action first | Stack | LIFO fits undo-style retrieval |
| Oldest waiting print job first | FIFO queue | First arrival is removed first |
| Maintain a numbered playlist | List | Order and positional operations matter |
| Keep unique student IDs for club attendance | Set | Membership and uniqueness matter |
| Find a student record from an ID | Map | The key identifies an associated value |
Explain the link between the requirement and the operation semantics. “Use a stack because it is fast” is incomplete: fast for which operation, on which implementation and input size?
A real application may combine ADTs. A portal can use a map for lookup, a queue for pending work and a stack for local undo actions.
20 | CHANGING IMPLEMENTATION WITHOUT BREAKING CALLERS
Suppose the editor first uses ListStack and later uses LinkedStack. A caller that only uses push, pop, peek, size and is_empty can keep the same code if both implementations satisfy the required contract.
A caller that edits stack._items directly depends on one representation and fails when that field disappears. Encapsulation supports the ADT boundary by keeping representation-specific work inside its implementation.
Substitution also depends on error and capacity policies. Replacing an unbounded-in-the-model stack with a small bounded stack changes valid requests unless the caller’s contract already allowed a full-stack rejection. Preserving method names alone is insufficient.
21 | PERFORMANCE DEPENDS ON REPRESENTATION
| Operation / storage | List-based example | Linked example |
|---|---|---|
| push | Amortized O(1); occasional resize can cost O(n) | O(1) link work under a unit-cost allocation model |
| pop / peek at top | O(1) for the shown end operations | O(1) |
| Extra structural storage | List capacity may include spare slots | Each node stores a link and object overhead |
| size | O(1) using stored length | O(1) using maintained count |
These costs belong to the stated implementations and cost model; LIFO itself does not guarantee them. Runtime allocation, resizing and garbage collection can affect measured timing. A linked implementation is not automatically more memory-efficient.
An ADT specification may include performance requirements when those are part of the intended contract. Then a replacement must meet those requirements as well as the logical behaviour.
22 | TEST THE SAME CONTRACT AGAINST BOTH
def check_stack(StackClass):
stack = StackClass()
assert stack.is_empty() and stack.size() == 0
stack.push("A")
stack.push("A")
assert stack.size() == 2
assert stack.peek() == "A" and stack.size() == 2
assert stack.pop() == "A"
assert stack.pop() == "A"
assert stack.is_empty()
try:
stack.pop()
except IndexError:
pass
else:
raise AssertionError("Empty pop must fail")
assert stack.size() == 0
check_stack(ListStack)
check_stack(LinkedStack)
Run these tests with both implementations defined. The same tests check empty construction, duplicate values, non-removing inspection, removal and empty rejection. A separate ordered pair such as A then B should also verify LIFO order rather than only repeated equal values.
Contract tests concentrate on observations callers are entitled to rely on. Implementation tests can additionally inspect internal consistency, such as the linked count matching the number of nodes.
23 | BENEFITS FOR MODULAR PROGRAMS
An ADT gives callers a stable vocabulary and behaviour to depend on. Separate developers can work on the application and implementation using the same agreed contract. Tests can check a new representation against existing expected behaviour.
This supports reuse and maintenance: an undo component can be written for a stack interface and reused with suitable implementations. It also makes reasoning easier because the caller does not need to understand every storage pointer before using pop.
The abstraction has to be meaningful. A badly specified contract creates uncertainty, while unnecessary wrappers around a one-off operation can add complexity without useful separation.
24 | COMMON MISUNDERSTANDINGS
| Claim | Correction |
|---|---|
| ADT means abstract class | An ADT is a specification; an abstract class is a language feature |
| Stack always means an array | An array or linked structure can supply LIFO behaviour |
| Correct names prove correct behaviour | The operations must satisfy their semantics and policies |
| Unordered set means random output every time | It means no particular sequence is promised by the ADT |
| Queue and stack are the same if both use nodes | FIFO and LIFO are different contracts |
| Changing storage always preserves behaviour | Capacity, failure and performance requirements may differ |
25 | EXPLAIN WITH A CONCRETE CHANGE
A strong explanation starts with the high-level contract: the editor requires a LIFO history with push, pop and peek. It then separates representation: ListStack stores its top at the end of a list, while LinkedStack stores it at the first node.
Link the ideas: because the caller depends on those operations rather than storage fields, a compatible implementation can replace another without changing the editor’s history calls. Therefore representation independence can improve modularity and maintenance.
Avoid saying that nothing can change. Internal memory use and performance may differ, and the replacement must still meet any requirements that the caller relies on.
26 | DESIGN AN ADT BEFORE IMPLEMENTING IT
Design a task queue for a school help desk. Specify permitted task values, initial state, enqueue, dequeue, inspect-front and size. State the ordering rule and the empty behaviour. Decide whether there is a fixed maximum capacity and what happens when it is reached.
Then propose two representations and explain how the caller would use the same public operations. You do not need to build a complete linked queue yet. The aim is to separate a precise logical description from the implementation choices.
The next lesson evaluates singly, doubly and circular linked lists, building on the node idea introduced here.