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

• For example:

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

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

Start = 1 NextFree = 4

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

4. The pointer field of the word ‘Orange’ is updated to point to ‘Apple’ at position 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

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