Key Idea: A data structure is chosen for the operations it makes cheap. Direct access, insertion in the middle, and order of removal pull in different directions — so the right answer depends entirely on what the program does most.
Paper 1
- Short definitions and a trace.
- State, identify, outline — precise terms.
Paper 2
- Write or correct Python for a scenario — your paper is the Python version, option B.
- Construct, determine, suggest.
Both
- Trace tables and justified choices earn method marks even when the final answer slips.
📦 Static against dynamic
| Array (static) | Linked list (dynamic) | |
|---|---|---|
| Size | Fixed at creation | Grows and shrinks with the data |
| Access by index | One calculation | Follow n references |
| Insert in the middle | Shift everything after it | Change two references |
| Memory per item | Just the value | Value plus a reference |
An array of n elements has n valid positions: 0 to n − 1 counting from zero. Reading index n is the classic out-of-bounds error — and in some languages it silently reads someone else's memory rather than failing.
🥞 Stack and queue
| Stack (LIFO) | Queue (FIFO) | |
|---|---|---|
| Add and remove | The same end | Rear in, front out |
| Order out | Last in, first out | First in, first out |
| Used for | Undo, back button, function calls | Print jobs, server requests |
| Its point | Reverse the most recent | Fairness — nobody is overtaken |
The details that get asked
- Overflow is pushing onto a full stack; underflow is popping an empty one
- Each function call pushes a frame holding locals and the return address
- Recursion with no base case exhausts that stack — a stack overflow
- A simple array queue wastes the space freed at the front; a circular queue wraps using a remainder
- A priority queue serves by urgency, so low-priority items can starve unless priorities age
Important: The change to reverse is the most recent one. A queue would undo the oldest change first, leaving the document in a state it was never in.
📝 Exam-style questions
A stack is empty. The operations PUSH 7, PUSH 2, POP, PUSH 9, PUSH 4, POP, PUSH 1 are carried out. Determine the contents of the stack, top first.
🔒 Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
A hospital triage system holds patients waiting to be seen. Suggest a suitable data structure, justifying your choice and identifying one problem it creates.
🔒 Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
✅ Quick check
Cover the answers.
Why is undo a stack rather than a queue? The change to reverse is the most recent — LIFO. A queue would undo the oldest first.
Where is the valid index range of an array of n elements? 0 to n − 1 counting from zero. Index n is out of bounds.
What causes a stack overflow in recursion? No base case — every call pushes a frame and none ever returns, until the call stack is exhausted.
Why does a dynamic array double rather than grow by one? Growing by one copies about n² elements in total; doubling makes the average cost per insertion constant.
What is starvation in a priority queue? A low-priority item is overtaken indefinitely. Fixed by ageing — raising priority with waiting time.
Exam tips
- Redraw the structure after EVERY operation, with the top or front labelled.
- Check pushes minus pops against the number of items left.
- Array for fixed size and index access; linked list for frequent insertion and removal.
- Say WHY the order matters — LIFO for reversal, FIFO for fairness.
- Overflow is a full stack, underflow an empty one. Do not swap them.
- Naming a structure earns one mark; the justification earns the rest.