Usually linked lists are drawn like this
Today im going to show a more concrete way to think about linked lists. Imagine you are setting up an Easter Egg hunt event. You will be putting lots of easter eggs (data) and address cards (next) in different houses. The goal for the kid is to collect all easter eggs.
For example, this easter egg hunt event have 6 houses. These houses are all far apart from each other, so the kid doesnt actually know where are all the houses. They need an address card (pointer) in order to go anywhere.
Now let the easter egg hunt begin! But we have an issue: the kid have no idea where to go first. To solve this, we need to give the kid an address card first. This is the equivalent of the head pointer in linked lists.
Now the kid will arrive at 41 College, collect easter egg #13, and do something to it (maybe eat it) This is the same as doSomething(current->data);. They also find a new address card saying 25 Spadina. The kid will take the new card. This is the same as Node* nextNode = current->next;
Next, the kid will go to the next house, which is 25 Spadina. This is the same as current = nextNode;
Then, they do all the same things again: collect the egg, do something to the egg, take the address card, and go to the next house by following the address card (15 Queen).
This will keep repeating. Eventually they will reach 77 Queen.
We know that the easter egg hunt has ended, but the kid doesnt. They will keep on going and follow the next card. However, 84 College is not part of the easter egg hunt! It is actually an office building and the kid is not allowed to get in. So the kid now panics. This is a segmentation fault, caused by visiting an invalid address.
As the organizer, you can solve this by making sure the last house’s address card says “STOP” instead of an address. This is the same as nullptr
So now the kid knows that they should keep on easter egg hunting until they see STOP. this is
while (current != nullptr)
Lets say today you feel evil, and changed the STOP to the address of 41 College.
What will happen? The kid now will go back to the starting point, and get stuck in a loop forever. This is a circular linked list, where the last node points back to the head.
Now the kid is angry, and wants to burn down all houses.
Being a stupid kid, they just immediately burns down the house in front of them: 41 College. This is delete current;
After this, now the kid have no idea where to go next. So the kid failed to burn all houses. This is a memory leak because now the kid is lost (the computer no longer knows how to get to all other houses)
A solution for the kid is that they should have took the address card before burning down the house, this way they know where to go next to continue burning down houses. This is why we need Node* nextNode = current->next; before delete current;
To burn down all houses, they now go to the next house and repeat, until they found the house with STOP.
[5 min vid] https://www.youtube.com/watch?v=F8AbOfQwl1c
