The big idea: An abstract data type says what operations a structure offers and what they do, not how they are built.
A stack: 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 answer broken into clear points, with guidance on how each point earns marks.