The big idea: An abstract data type says what operations a structure offers and what they do — not how they are built.
A stack promises push, pop and peek with last-in-first-out behaviour. Whether it is an array or a linked list underneath is nobody else's business.
| Abstract data type | Data structure | |
|---|---|---|
| Describes | What you can do and what it means | How it is stored |
| Example | Stack, queue, list, set, map | Array, linked list, hash table, tree |
| Chosen for | The behaviour the program needs | The performance that behaviour needs |
| Can change | Rarely — callers depend on it | Freely — nobody outside can tell |
The word abstract is doing real work: Abstract here means the detail is deliberately hidden, not that it is vague.
The promise is exact: pop returns the most recently pushed item. What is vague is only the implementation — and that vagueness is what lets it be replaced.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
You can swap it
- Start with an array; switch to a linked list when insertion becomes the bottleneck
- No calling code changes — the operations are the same
- The decision stays in one file instead of every file
You can reason about it
- "It is a queue" tells you the order things come out
- You do not have to read the implementation to predict behaviour
- Bugs narrow to one place: the implementation, or the use
It cannot be misused
- A stack offers no way to reach the middle
- So no code CAN reach into the middle and break the invariant
- The restriction is the guarantee
Every language ships them: Python's list, dict and set; Java's ArrayList, HashMap and HashSet. You have been using ADTs since your first program — the operations were documented, the internals were not.
Feeling unprepared for exams?
Get a clear study plan, practice with real questions, and know exactly where you stand before exam day. No more guessing.
Ask what the program does MOST
- Need the most recent item back first → stack
- Need fair order, first come first served → queue
- Need to look things up by a key → map (dictionary)
- Need membership and no duplicates → set
- Need position and ordered traversal → list
Name the operation, not the vibe: "A set is better here" earns little. "Membership is checked on every one of 10,000 records, and a set checks membership in O(1) where a list is O(n)" earns the marks.
Justify from the operation the program repeats most.
How this is tested — you must separate what a structure PROMISES from how it is built, and justify a choice from the operations a program actually performs. It comes up two ways:
Paper 2 — working with code
- Explain the purpose of an ADT, 3-4 marks
- Distinguish an ADT from a data structure
- State why hiding the implementation helps
Paper 2 — the algorithmic-thinking question
- Choose an ADT for a described program and justify it
- Say what would go wrong with the alternative
The classic trap: Describing an array when asked about a list. The array is an implementation; the list is the ADT. Answers that go straight to storage have skipped the question.
The contract above the line; array or linked list below it.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
A program stores the usernames already taken on a site and checks each new sign-up against them. Explain which ADT is appropriate and why, referring to the operations involved.
Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.