The big idea: A linked list stores each value in its own node, and each node holds a reference to the next one.
Nothing has to sit next to anything else in memory. The order lives in the references, not in the addresses.
Step through to the insert scenes: four elements shifting in the array against two references changing in the list.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
Asked to sketch a linked list after an insertion or deletion? Draw every node as a box with a data part and a pointer part, and draw the pointers as arrows. Change pointers in this order:
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.
Singly linked
- Each node points forwards only
- Traversal runs one way, from the head
- Smallest memory — one reference per node
- To delete a node you must already hold the one before it
Doubly linked
- Each node points forwards and backwards
- Traversal runs either way; deletion needs only the node itself
- Two references per node — more memory
- Two links to update on every insertion and deletion
Circular
- The last node points back to the first
- There is no null end — traversal can loop forever
- Suits round-robin turn-taking and buffers
- Needs a stopping rule, or the loop never terminates
The circular trap: A circular list has no null to stop at. A traversal written the usual way — "while current is not null" — runs forever.
Stop when you return to the node you started at, and say so in an exam answer.
Never wonder what to study next
Get a personalized daily plan based on your exam date, progress, and weak areas. We'll tell you exactly what to review each day.
| Operation | Array | Linked list |
|---|---|---|
| Reach element n | O(1) — calculated | O(n) — followed |
| Insert at the front | O(n) — shift everything | O(1) — two references |
| Insert in the middle | O(n) | O(n) to find, O(1) to link |
| Memory per item | Just the value | Value plus a reference |
| Size | Fixed at creation | Grows and shrinks |
| Search for a value | O(n), or O(log n) by binary search if sorted | O(n) — binary search is impossible without direct access |
The trade in one line: A linked list gives up direct access and gets cheap insertion and removal in return.
So: does the program mostly read by position, or mostly insert and delete? That question decides it, and nothing else does.
Caching matters more than the table suggests: An array's elements sit together, so reading one pulls its neighbours into cache and the next read is already there. A linked list's nodes are scattered, so each hop can be a cache miss.
In practice an array often beats a linked list even where the complexity says otherwise.
How this is tested — you must weigh direct access against cheap insertion, using the operation the program actually repeats. It comes up two ways:
Paper 2 — working with code
- Evaluate linked lists against arrays, 4-6 marks
- State an advantage AND a disadvantage
- Identify which kind of list a scenario needs
Paper 2 — the algorithmic-thinking question
- Justify a choice for a described program
- Say what the alternative would cost
The classic trap: Writing "linked lists are dynamic so they are better". Evaluate demands both sides and a judgement tied to the scenario — an unqualified "better" earns nothing.
A music app keeps the current playlist, where users constantly drag tracks to new positions and delete them, but rarely jump to "track 47". Evaluate the use of a linked list rather than an array.
Model answer plan
See the answer broken into clear points, with guidance on how each point earns marks.