| Removing from 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 remove the data "Bert" from the above linked list it would look like the table below.
| 0 | 2 | |
| 1 | Fred | 8 |
| 2 | 4 | |
| 3 | 6 | |
| 4 | 3 | |
| 5 | Bert | 0 |
| 6 | 9 | |
| 7 | x | |
| 8 | Charlotte | x |
| 9 | 7 |
- StartOfList = 1
- FreeSpace = 5
The changes have been marked in a rather fetching puke green :) Bert has been removed and that node has been added to the start of the free space list (we could add it to the end but i find it quicker in code to do it this way!). What is essentially appening is that you are "skipping" over the node to be removed rather than actually removing it. "Fred" is now pointing to "Charlotte" and "Bert" has been added to the free space list.
Note - The data held in the removed node is not actually deleted. This is because it will be overwritten over time so there is no point to delete it. Deleting the data would take more computation time when it is not needed. This is very common when removing anything in computing. Memory and files both work in the same way!
- Look at the node pointed to by "StartOfList" pointer.
- If the node is not the one we are looking for then follow the pointer and repeat this step.
- If the end of the list has been reached and the node could not be found then a error is returned.
- If found then the previous node will be linked to the pointer of the node to be removed.
- The removed node's pointer will point to "FreeSpace" pointer
- "FreeSpace" pointer will finally point to the removed node.
