A linked list is a dynamic data structure where each item holds its own data and a pointer to the next item in the sequence. Unlike an array, items do not sit in consecutive memory locations — they can be scattered, with each node guiding you to the next one.
What is a linked list?
A linked list is a dynamic data structure in which each element, called a node, stores two pieces of information:
- Data — the actual value (a number, a name, or any other piece of information).
- Pointer (also called a next reference) — the memory address of the next node in the sequence.
The list begins at a special reference called the head, which points to the first node. The last node's pointer is set to null (or None in Python) to signal the end of the list.
Head
↓
[Alice | →] → [Bob | →] → [Carol | →] → [David | null]
How does a linked list differ from an array?
Arrays store all their elements in consecutive memory locations — like a row of numbered seats in a cinema. The computer can jump straight to seat 7 without looking at seats 1 to 6. A linked list stores nodes anywhere in memory and stitches them together with pointers — like a treasure hunt scattered across a building.
| Feature | Array | Linked list |
|---|---|---|
| Memory layout | Contiguous (adjacent) | Scattered (anywhere) |
| Access by index | O(1) — instant random access | O(n) — must follow pointers from head |
| Inserting an item | O(n) — must shift items along | O(1) — update two pointers |
| Deleting an item | O(n) — must shift items along | O(1) — update one pointer |
| Size fixed at creation? | Often yes (static array) | No — grows/shrinks freely |
| Memory overhead | Low | Higher (each node stores a pointer) |
How do you insert a node into a linked list?
Insertion does not require shifting any existing data. You simply create a new node and adjust two pointers. To insert Carol between Bob and David:
Before:
[Alice | →] → [Bob | →] → [David | null]
Steps:
- Create a new node:
[Carol | null] - Set Carol's pointer to point at David.
- Set Bob's pointer to point at Carol.
After:
[Alice | →] → [Bob | →] → [Carol | →] → [David | null]
No data was moved — only pointers changed. For a large dataset this is far faster than inserting into the middle of an array.
How do you delete a node from a linked list?
To delete Bob, simply update Alice's pointer to skip over Bob and point directly to Carol. Bob's node is then unreachable from the list and the memory can be reclaimed.
Before: [Alice | →] → [Bob | →] → [Carol | null]
After: [Alice | →] → [Carol | null] (Bob is bypassed)
Again, no data is physically moved — a single pointer update is all that is required.
What are the types of linked list?
| Type | Description |
|---|---|
| Singly linked list | Each node points only to the next node. Traversal is one-direction only. |
| Doubly linked list | Each node has two pointers: one to the next node and one to the previous. Traversal possible in both directions. |
| Circular linked list | The last node's pointer loops back to the head rather than being null. Used in round-robin scheduling. |
At GCSE level, the singly linked list is the most commonly examined.
When are linked lists used in practice?
Linked lists underpin several common computing structures:
- Stacks and queues can be implemented using linked lists, where push/pop and enqueue/dequeue operations involve updating the head or tail pointer.
- Undo history in applications — each action is a node; undoing walks backwards through the list.
- Playlist management — music players traverse a linked list of tracks, easily inserting or removing songs without reshuffling the whole collection.
- Memory allocators inside operating systems maintain free-memory regions as linked lists.
What should I be able to do in the GCSE exam?
Examiners typically ask you to:
- Draw a linked list diagram showing nodes, pointers, and the head reference.
- Trace through an insertion or deletion, showing which pointers change.
- Explain one advantage of a linked list over an array for a given scenario.
- Explain one disadvantage of a linked list over an array.
Use the words dynamic, pointer, node, head, and null in your answers — they are the markers that signal accurate understanding.
Frequently asked questions
Why can't I access the fifth element directly in a linked list?
Because the nodes are scattered in memory — there is no arithmetic shortcut to find node 5. The computer must start at the head, follow pointer 1, then pointer 2, all the way to node 5. This is called sequential access and takes O(n) time in the worst case.
Is a linked list the same as a Python list?
No. Python's built-in list is implemented internally as a dynamic array (a contiguous block of memory that resizes when full). A linked list is a conceptually separate data structure with different performance characteristics.
When would I choose a linked list over an array?
Choose a linked list when insertions and deletions happen frequently in the middle of the collection, and when you do not know the size of the collection in advance. Choose an array when you need fast random access (jump to any element instantly) and the size is predictable.
Do I need to implement a linked list in Python for GCSE?
Some controlled assessment tasks may ask for a linked list implementation. You would typically represent each node as a class with data and next attributes, and the list itself as a class holding the head reference. Check your specification for whether implementation is required or whether understanding the concept is sufficient.
Struggling to visualise pointer changes? Visit aitutors.me — Professor Turing will draw linked list diagrams with you in real time and guide you through insertion and deletion step by step.