Key Idea: An abstract data type says what operations a structure offers and what they mean — never how it is built. That separation is the whole unit: it lets an implementation be replaced for a faster one without a single caller changing.
Paper 1
- Define an ADT; state a property of a structure.
- Give the result of a set operation or a traversal.
Paper 2
- Construct or trace linked-list and tree operations.
- Evaluate a choice against an alternative.
Both
- Justify from the operation the program repeats most, with its complexity.
🗝️ ADT against data structure
| Abstract data type | Data structure | |
|---|---|---|
| Describes | What you can do, and what it means | How it is stored |
| Examples | Stack, queue, list, set, map | Array, linked list, hash table, tree |
| Chosen for | The behaviour needed | The performance that behaviour needs |
| Can be changed | Rarely — callers depend on it | Freely — nobody outside can tell |
A stack offers no way to reach the middle, so no code can reach the middle and break last-in-first-out. The thing it refuses to do is the thing it promises.
🔗 Linked lists
| Singly | Doubly | Circular | |
|---|---|---|---|
| Points | Forwards only | Both ways | Last node → first |
| Memory per node | One reference | Two | One |
| Traversal stops at | None | None | The head again |
| Deleting needs | The node before | Only the node | The node before |
The operations
- Traverse from the head until None — there is no other route in
- Insert: point the new node forwards first, then repoint the previous one
- Delete: route around it — prev.next ← target.next. Nothing is erased
- The head is always the special case: it has no previous node
- Reaching the nth element is O(n); inserting once in position is O(1)
Important: Writing prev.next ← new before new.next ← prev.next overwrites the only reference to the rest of the list. Every node after that point is orphaned, and nothing reports it.
🌲 Binary search trees
One rule and its consequences
- For every node: left subtree smaller, right subtree larger — all descendants, not just children
- Search discards an entire subtree per comparison
- Insert is a search that ends at an empty child
- In-order traversal — left, node, right — returns the values sorted, free
- Cost is the height: about log₂ n balanced, but n if values arrive in sorted order
A BST is O(log n) while balanced. The same values inserted in ascending order give a single line — height n, and O(n). The shape depends entirely on insertion order.
🎯 Sets and hash tables
| Operation | Meaning | {1,2,3} and {3,4} |
|---|---|---|
| Union ∪ | In either | {1, 2, 3, 4} |
| Intersection ∩ | In both | {3} |
| Difference − | In the first, not the second | {1, 2} — not symmetric |
What a hash table does
- The key computes its own address: hash it, take it modulo the table size, go there
- A good hash function is deterministic, fast and uniform
- Collisions are inevitable — more possible keys than buckets, which is arithmetic
- Chaining keeps colliding keys in a list inside the bucket
- O(1) on average, O(n) worst case — clustering is what destroys it
📝 Exam-style questions
A hospital system must find a patient by ID instantly, and must also print every patient in ID order each night. Evaluate a hash table against a binary search tree for this.
🔒 Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
Write a Python function that counts how many nodes a singly linked list holds, and state its complexity and why it cannot be improved without changing the structure.
🔒 Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
✅ Quick check
Cover the answers.
ADT or data structure: a hash table? Data structure — one way to implement a map or a set. The map is the ADT.
Why must a new node be linked forwards first? Repointing the previous node first overwrites the only reference to the rest of the list, orphaning everything after it.
What does an in-order traversal of a BST return? Every value in ascending order, with no sorting step — the ordering is already in the structure.
Is a − b the same as b − a? No. Difference is the one set operation whose order matters.
Why is a hash table O(n) in the worst case? A hash function that clusters keys into few buckets makes one chain the whole table, so lookup becomes a linear search.
Exam tips
- ADT = what it promises. Data structure = how it is built. Say which you mean.
- Justify every choice by the operation the program repeats most, with its complexity.
- Link a new node forwards BEFORE repointing the previous one.
- Handle the head separately — it has no previous node, and examiners pick that case.
- O(log n) while balanced · O(1) on average — never drop the qualification.
- Evaluate needs both sides AND a verdict. The verdict is its own mark.