In simple terms
A friendly intro before the formal notes — no formulas yet.
The Data Conga Line
Linked lists are a way to store data in a chain, where each item points to the next. This makes it easy to add or remove items anywhere in the chain without shifting everything else.
Imagine a treasure hunt. Each clue (a 'node') has a piece of treasure (the 'data') and tells you where to find the next clue (the 'pointer'). The first clue is the 'head', and the last clue says "End of hunt" (a 'null' pointer). You can't just jump to the middle; you have to follow the clues in order from the start.
- 1
A 'node' is created, holding a piece of data and an empty 'next' pointer.
- 2
The first node is designated as the 'head' of the list, which is our only entry point.
- 3
A new node is added by making the previous node's pointer link to it.
- 4
The final node in the chain has a 'null' pointer, indicating the end of the list.
Explore the concept
Use the live diagram and synced steps — play it or tap a step card to walk through.
Full topic notes
Formal explanation with the rigour you need for the exam.
The Anatomy of a Linked List
A linked list is not stored as a contiguous block in memory like an array. Instead, it is a collection of individual objects called nodes. Each node is a simple structure with two essential components:
The entire list is accessed through a single starting point: a pointer called the head. This points to the first node. From there, you can follow the next pointers from node to node. The next pointer of the very last node in the list points to null, which is a special value indicating there are no more nodes. This prevents us from trying to access memory that doesn't belong to our list.
Data: The actual value we want to store (e.g., an integer, a string, a more complex object).
Pointer (or Reference): A memory address that 'points' to the next node in the sequence. We'll often call this the next pointer.
Core Operations on Singly Linked Lists
The dynamic nature of linked lists is realised through a set of core operations. Understanding how to traverse, insert, and delete nodes is crucial.
Traversal: The process of visiting every node. You start with a temporary pointer, current, set to head. In a loop, you process current.data, and then advance the pointer by setting . The loop terminates when current becomes null.
Insertion: To add a new node, you first create it. Then, you adjust pointers to fit it into the list. Inserting at the head is a special case where the main head pointer must be updated to point to the new node. Inserting elsewhere involves changing the next pointer of the previous node.
Deletion: To remove a node, you must find its predecessor (the node before it). The predecessor's next pointer is then updated to point to the node after the one being deleted, effectively bypassing and removing it from the chain. Deleting the head node is again a special case requiring an update to the main head pointer.
Evaluation: Linked Lists vs. Arrays
Choosing between a linked list and an array is a classic design decision that depends entirely on the problem's requirements. There is no universally 'better' option; each has distinct advantages and disadvantages that you must be able to analyse for the exam.
Size & Memory: Arrays have a fixed size declared at compile time, which can lead to wasted memory or overflow errors. Linked lists are dynamic and grow/shrink at runtime, using memory more efficiently for lists of unknown size.
Memory Layout: Arrays require a single, contiguous block of memory. Linked lists can be scattered throughout memory, which can be an advantage if memory is fragmented.
Insertion/Deletion Speed: Linked lists excel here. Inserting or deleting an element in the middle of a list is an O(1) operation (once the position is found), as it only involves redirecting pointers. For an array, this is an O(n) operation because subsequent elements must be shifted.
Access Speed: Arrays excel here. Accessing an element at a specific index (e.g., myArray[i]) is an O(1) operation. For a linked list, this is an O(n) operation as you must traverse the list from the head to the nth element.
Summary: Use an array when you have a fixed number of elements and require frequent, fast random access. Use a linked list when the number of elements is unknown or changes frequently, and you perform many insertions or deletions.
Examiners love to test your understanding of edge cases in linked list algorithms. Before finalising your pseudocode, always ask yourself: 'What happens if the list is empty (head is null)?', 'Does my code correctly handle operations on the first node (changing the head)?', and 'Does it work for the last node?'. Writing down these checks and ensuring your algorithm handles them is a key to scoring full marks.
Worked examples
See the formulas applied — reveal one step at a time, like the exam.
A singly linked list of integers is sorted in ascending order. The list is accessed via a head pointer. Write an algorithm in pseudocode to insert a new integer, value, into the list while maintaining the sorted order.
- 1
A new node is created with the given value.
A singly linked list stores student names, accessed by a head pointer. Write an algorithm in pseudocode to delete the node containing a specific targetName.
- 1
First, handle the edge case of an empty list.
How it all connects
The big idea sits in the middle — tap a linked idea to explore the link.
Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.
Glossary
Try to recall each definition before you reveal it.
Quick check
Answer in your head first — then tap to check. No pressure.
Revision flashcards
Flip the card. Test yourself before the exam.
What is a node in a linked list?
A fundamental unit of a linked list, typically an object, containing two parts: the data being stored and a pointer (or reference) to the next node in the sequence.
Key takeaways
Review these before you close the topic — retrieval beats re-reading.
- ✓
Data: The actual value we want to store (e.g., an integer, a string, a more complex object).
- ✓
Pointer (or Reference): A memory address that 'points' to the next node in the sequence. We'll often call this the next pointer.
Practice — then mark it
The whole point: a real Cambridge question, marked mark-by-mark.
Test Your Knowledge on Linked Lists
Test Your Knowledge on Linked Lists
Extra simulations & links
PhET, GeoGebra and other curated tools — open in a new tab.
Frequently asked
Checkpoint
One marked question is worth ten re-reads — close the loop before you move on.
Reading it isn’t knowing it — prove it.
Before you move on: do Test Your Knowledge on Linked Lists on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.