December 10, 2017 · Computer Science Data Structures

Linked List as Scavenger Hunt

An analogy for the linked list data structure is a city-wide scavenger hunt. Imagine you're a participant in the hunt and you're given the location of the first scavenger hunt item. So you go to the first item. Attached to the first item is a post-it note containing a hint to find the location of the second item. So you go to the second item. And attached to the second item is a post-it note containing a hint to find the location of the third item. And so on. So if you want to get to the last item, there's no way to get there directly. You'll have to sequentially visit the first item, then the second item, then the third item, ... etc. until you finally reach the last item.

scavenger hunt

Similarly, when you work with a linked list, you're only given access to the first node, or head node. The head node has knowledge about where the second node is. And you can use this knowledge to traverse to the second node. Of course, the second node also has knowledge about where the third node is. So if you're at the second node, you can traverse to the third node. This process repeats until you get to the very last node.

linked list

How do you know you're at the last node? Well, the last node is not going to have any knowledge about any subsequent node. So you reach a dead end. In linked list terminology, you've reached the tail node.

Adding an item

What if we're an organizer of the event and we want to add a brand new scavenger hunt item? Let's say we want to add this item to the very end of the scavenger hunt. This would elongate the hunt and make it the new last item. We need to do two things to accomplish this:

Adding to the end of the scavenger hunt
  1. First, we need go to the current last item. Of course, we still have to visit each item sequentially in order to get there. (Not even the organizers of the scavenger hunt can get to the last item directly!).
  2. Once we're at the current last item, we notice that it has no post-it note pointing to any next item. After all, that's how we knew we were at the current last item in the first place! So we put a brand new post-it note where there previously was none. And this post-it note should contain a hint that leads to the location of the new last item.

And we're done! We can now get from the first item, to the second item, to the third item, ... etc. all the way to the previous last item, and finally to the new last item.

Inserting into the middle of the scavenger hunt

But what if we want to insert an item into the middle of the scavenger hunt? For instance, what if we want to add a new item between the third and fourth items? Now there are three things we need to do:

  1. First, we of course need to go to the spot where we want to insert. Specifically, we need to go to the third item by sequentially visiting the first item, then the second item, and then the third item.
  2. Now we need to switch out the post-it note attached to the third item. Before it contained a hint leading to the fourth item. We want to switch it out for a post-it note that leads to the new item instead. And voila! We can get to the new item from the third item now!
  3. If we stop there though, the new item will be a dead end, since there's no post-it note attached to it yet. What we really want to do is create a path from the new item to what was previously the fourth item (about to be the fifth item). Wait a minute, didn't the third item have a post-it note leading there? We switched it out for a new post-it note in step 1, but let's not throw that old note away just yet. The old note contains a hint leading to what was previously the fourth item (about to be the fifth item). This is exactly what we need, so we can simply slap the old note onto the new item.

And that's it! We can now go from the first item, to the second item, to the third item, to the new item (now fourth), to the previous fourth item (now fifth), and so on.

Inserting into a linked list

In a nutshell, we basically need to rearrange some pointers whenever we want to insert something into a linked list. That involves traversing to the node directly before where we want to insert. Now this node currently already points to a subsequent node, but we want to change it to point to the new node. And if we're inserting anywhere except the end of the list, we also want to set up the new node so that it points to what its previous node used to point to before we changed it. It's much easier to visualize this than to read about it. It looks like this:

linked_list_insertion

In the diagram above, the third node used to point to the tail node. But in order to add our new item, we delete that pointer and replace it with a pointer to the new item. Finally, we then set the new node to point to the tail node.

Deleting an item

In order to remove an item from the scavenger hunt, we just need to not lead the players of the game there anymore! So we need to get rid of the post-it note that leads to the item we want to delete. And in case the item we're deleting isn't the last item in the hunt, we replace the trashed post-it note with a post-it note leading to the new next item.

In linked list terminology, this means that we again have to traverse to the node directly before the node we want to delete. We then need to change this node to point to the node that comes after the one we want to delete. (If there's no node that comes after the one we want to delete, then we change the node to point to nothing). So now the node that we want to delete no longer has anything that refers to it, and can be garbage collected. Again, it's much easier to visualize this than to read about it. It looks like this:

linked_list_deletion

In the diagram above, the second node used to point to the third node. But in order to delete the third node, we delete that pointer and replace it with a pointer to the tail node. And we point to the tail node, because the tail node is the node that comes after the third node. Now there's nothing pointing to the third node, so it can safely be garbage collected and effectively deleted.

That's it!

I hope the scavenger hunt analogy helps you understand linked lists better. Stay tuned as we discuss arrays as a data structure next time!