| Adding to a linked list |
| 0 | 2 | |
| 1 | Fred | 5 |
| 2 | 4 | |
| 3 | 6 | |
| 4 | 3 | |
| 5 | Bert | 8 |
| 6 | 9 | |
| 7 | x | |
| 8 | Charlotte | x |
| 9 | 7 |
- StartOfList = 1
- FreeSpace = 0
If we wanted to add the data "Betty" to the above linked list we would put it in position 0. The new list would look like -
| 0 | Betty | x |
| 1 | Fred | 5 |
| 2 | 4 | |
| 3 | 6 | |
| 4 | 3 | |
| 5 | Bert | 0 |
| 6 | 9 | |
| 7 | x | |
| 8 | Charlotte | 0 |
| 9 | 7 |
- StartOfList = 1
- FreeSpace = 2
The changes have been marked in a rather fetching puke green :) The new data has been added to the first free space block. The previous end of the list now points to the new data element and the FreeSpace pointer now points to the next free space. There is a very specific algorithim which needs to be followed which is shown below.
- Look at the node pointed to by the "startOfList" pointer
- Follow the pointers until you reach the end of the list.
- Make this pointer point to "freeSpace" (the start of the free space list)
- Add the data to the node pointed to by "freeSpace"
- Set the "FreeSpace" pointer to be the next free node (follow the pointer from the new node)
- Set the new nodes pointer to be x (or null)
Note - The first free node is always the node pointed to by the FreeSpace pointer. It is not always going to be the free block with the lowest pointer!
Note - The exam may use different names for the pointers. There is no right name for them so just be aware!
Note - This way of doing a linked list would be laughed out of most programming circles for various resons. Don't ask me why the exam board insist on doing it this way! I guess it is probably due to complexity but I do not think the "proper" way is that much more complicated.
