Pointers in Linked Lists

In this assignment, we will explore an analogy to help you better understand how to work with pointers in Linked Lists. Even if the solution to the problem in the previous assignment made sense to you, we have observed that students often need help understanding how to use pointers in practice when dealing with linked list problems. For example, they face difficulties in understanding what happens when a pointer is moved using operations like curr = curr.next.

Cats & Balloons

To aid your understanding of pointers in Linked Lists, we will employ the assistance of cats. Yes, cats! They will help us visualize the concept.

Let's imagine that nodes in a linked list are represented by balloons connected by strings, where each node corresponds to a single balloon. Cats will be our variables that hold balloons, akin to pointers that reference nodes in the linked list. For instance, if we have a linked list 1 -> 2 -> 3 -> null as an input, we will receive a head node with a value of 1, and the variable head will be like a lovely cat holding the balloon with the value 1. In our analogy, this can be represented as a cat named head clutching a balloon labeled 1.

If we were to reassign the head variable to null, it would mean that the cat no longer holds anything, and the balloons would fly away since nothing would reference them anymore.

Now that we comprehend the representation of cats and balloons, let's examine what happens when we encounter the following code:

let prev = null;
let curr = head;

In line with our analogy, we introduce two new cats named prev and curr. The prev cat does not hold any balloons, as its value is null, while the curr cat now holds the same balloon as the head cat. Hopefully, they won't engage in a feline feud over that balloon!

So, what does this mean for us? Essentially, if we later modify the reference of the curr variable (by doing curr = curr.next), and it starts pointing to the node with the value 2, the head variable will continue to hold a reference to the linked list with a value of 1. In our analogy, if the curr cat starts holding another balloon, the one with the value 2, the head cat will affirm, "Hey, I got you! I am still holding balloon 1." Consequently, at the end of the operation, we can safely return the head variable, as it still maintains the reference to that node, just like the cat still holds that balloon.

In the previous assignment, we also encountered the concept of sliding pointers. Let's explore how that translates here:

prev = curr;
curr = curr.next;

Initially, prev cat is holding null, and head and curr hold balloon 1.

What occurs next is prev = curr. Based on our analogy, the prev cat starts holding the same balloon as the curr cat, which is the same balloon held by the head cat in this case. We can see it's getting quite crowded in there.

Next, let's cover curr = curr.next part. The curr cat relinquishes balloon 1 and begins holding its next balloon, balloon 2 in this case. Consequently, even though we initially set curr = head, causing two cats to hold the same balloon (two variables referencing the same node), this is no longer the case after executing curr = curr.next. Now, the head and curr cats hold two different ballons (nodes). However, head and prev still hold the same balloon (node 1).

There is one aspect we haven't discussed yet: the behavior of curr.next.next. You might find yourself using this very often when solving problems with linked lists. Let's examine this using our analogy. The curr cat is clutching balloon 2.

When we evaluate curr.next.next, it advances to the next connected balloon and subsequently to the next one. However, since no more balloons are available, the curr cat won't have a balloon to hold (the variable will reference null).

If we were to attempt curr.next at this point, it would result in a reference error, as the cat no longer holds a balloon. Consequently, the next pointer does not exist.

While it may be a bit silly, hopefully, this analogy has aided your comprehension of pointers and nodes in linked lists. We will revisit it in future assignments to further solidify your understanding.