Linked Lists

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

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

TIP

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

Index	Data	Pointer
3	’Orange’

Start = 1 NextFree = 4

3. The pointer field of the word ‘Pineapple’ is updated to point to ‘Orange’, at position 3

Index	Data	Pointer
1	’Pineapple’	3

4. The pointer field of the word ‘Orange’ is updated to point to ‘Apple’ at position 0

Index	Data	Pointer
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

EXAMPLE

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.

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