Linked Lists (OCR A Level Computer Science): Revision Note
Linked Lists
What is a linked list?
In A Level Computer Science, a linked list is a dynamic data structure that is used to hold an ordered sequence
The items which form the sequence do not have to be in contiguous data locations
Each item is called a node and contains a data field alongside another address which is called a pointer
For example:
Index | Data | Pointer |
---|---|---|
0 | 'Apple' | 2 |
1 | 'Pineapple' | 0 |
2 | 'Melon' | - |
3 |
|
|
Start = 1 NextFree = 3
The data field contains the value of the actual data which is part of the list
The pointer field contains the address of the next item in the list
Linked lists also store the index of the first item as a pointer
They also store a pointer identifying the index of the next available space
Examiner Tips and Tricks
Linked lists can only be traversed by following each item’s next pointer until the end of the list is located
Linked Lists: Traversing, Adding & Removing Data
Traverse a linked list
Check if the linked list is empty
Start at the node the pointer is pointing to (Start = 1)
Output the item at the current node ('Pineapple')
Follow the pointer to the next node repeating through each node until the end of the linked list.
When the pointer field is empty/null it signals that the end of the linked list has been reached
Traversing the example above would produce: ‘Pineapple’, ‘Apple’, ‘Melon’
Adding a node
An advantage of using linked lists is that values can easily be added or removed by editing the points
The following example will add the word ‘Orange’ after the word ‘Pineapple’
1. Check there is free memory to insert data into the node
2. Add the new value to the end of the linked list and update the ‘NextFree’ pointer
3 | 'Orange' |
|
Start = 1 NextFree = 4
3. The pointer field of the word ‘Pineapple’ is updated to point to ‘Orange’, at position 3
1 | 'Pineapple' | 3 |
4. The pointer field of the word ‘Orange’ is updated to point to ‘Apple’ at position 0
3 | 'Orange' | 0 |
4. When traversed this linked list will now output: ‘Pineapple’, ‘Orange’, ‘Apple’, ‘Melon’
Removing a node
Removing a node also involves updating nodes, this time to bypass the deleted node
The following example will remove the word ‘Apple’ from the original linked list
1. Update the pointer field of ‘Pineapple’ to point to ‘Melon’ at index 2
Index | Data | Pointer |
---|---|---|
0 | 'Apple' | 2 |
1 | 'Pineapple' | 2 |
2 | 'Melon' | - |
2. When traversed this linked list will now output: ‘Pineapple’, ‘Melon’
The node is not truly removed from the list; it is only ignored
Although this is easier it does waste memory
Storing pointers themselves also means that more memory is required compared to an array
Items in a linked list are also stored in a sequence, they can only be traversed within that order so an item cannot be directly accessed as is possible in an array
Worked Example
A coach company offers tours of the UK
A linked list stores the names of cities on a coach tour in the order they are visited.

linked-lists-question
The tour is amended. The new itinerary is London, Oxford, Manchester then York. Explain how Birmingham is removed from the linked list and how York is added. You may use the diagram to illustrate your answer.
4 marks
Answer:
Example answer that gets full marks:
The first thing you need to do is change the Oxford pointer to go around Birmingham to point to Manchester. [1]

linked lists WE 1
Then you create a node called York and this is placed at the next free space in the list. [1]

linked lists WE 2
Manchester is kept in the same position and it’s pointer changed to point to York. [1]

linked lists WE 3
The York node then points to Null. [1]

linked lists WE 4
You've read 0 of your 5 free revision notes this week
Sign up now. It’s free!
Did this page help you?