Linked list coding challenge

Today, we’ll be solving a freecodecamp algorithm question: https://www.freecodecamp.org/learn/coding-interview-prep/data-structures/remove-elements-from-a-linked-list-by-index, removing an element from a linked list by index. Try to contain your excitement! 😂

---

We recommend reading Arrays and Lists 📚 before starting the coding exercise. This will ensure you have a firm understanding of the data structures used in the following exercise.

⚡ TL;DR: In linked list, elements are removed by linking the previous element with the next element, thus removing any link to the element to be removed.

Setup

Before we get started, let’s picture yourself waiting in line at the grocery store. The line you’re waiting in will be our linked list.

Each person can only see the person in front of them, but they can’t see who is behind them. Bummer! 😞

Now that we have an idea of what a linked list looks like, let’s set it up. We’ll do this in JavaScript.

The LinkedList has a head, this is the first Node of the list. Think of it as the last person standing in the line, they can see someone in front of them, but no one is standing behind them.

Each Node contains a value and a link to the next Node in the list.

Now, let’s create a list:

Here, our head‘s value is 0. The rest of the elements are called the tail.

Walking the list 🚶‍♀️

In this step we’re going to traverse the list, node by node. As we can see, we’re starting with a list of five elements. For now, we just want to look at every element of the list.

It’s important to remember that the last node in the list will be pointing to null (this is the person at the front of the line). Once we reach this node, node = node.next will set node to null and we will stop the iteration.

This is like asking to the last person waiting in line who’s in front of them, then asking the same thing to that person, until you reach the person at the front of the line.

Finding a node

Now that we know how to traverse the entire list, we want to find the one we’re looking for. For that we’re going to need a counter, to keep track of the number of nodes we’ve seen so far when walking the list.

With the counter going up with every node, we can now compare it to the given index. When our counter is equal to index, we know we’ve reached the node we want to remove:

Removing the node

Having done the heavy lifting in the previous steps, removing the node has become a lot easier!

Let’s go through the steps, one more time:

1. We initialize a few variables:
   • node, that we set to the head (first element) of our linked list,
   • counter, which we’ll use to track the index of the node we’re looking at in the while loop,
   • prev, which we’ll set to the previous element we looked at in the while loop.
2. We start our loop, with a condition that says “don’t stop unless node is null”
3. We compare our counter to the index we want to remove.
   • If they’re equal, it’s time to remove the node! We make the previous node prev point to the next node in the list, node.next – now, no node in the list points to the one we want to remove anymore!
   • If not, we just keep going, updating prev to be the current node, and node to be the next one. We also increment our counter.

Think of it this way: with our group waiting in line, if someone in the middle of the line leaves, then the person behind them can now see the next person in front of them.

Handling the edge cases

Now you might be wondering, what happens if the index is 0? Less than 0? What if it’s bigger than the length of our list? And you’re right, these are edge cases we will have to handle! Let’s see how we can do that:

As a bonus, here’s this question from leetcode. We’ll solve it, but with a twist. 🤔 Can you spot the error?

Hint: do you have a way of finding where the list starts?

Before you go…

Thanks for reading! If you enjoyed this article, please give it a like 👍 to help others find it. And do not hesitate to share your thoughts in the comments below.

💡 Tip of the week

Are you learning git commands? Here is a resource you can use so you don’t have to remember it all: https://ohshitgit.com/

🔗 What else is going on in tech?

• Are you ready for Facebook’s Metaverse?
• The first release candidate for Python 3.10 is out!
• Looking for a tech podcast recommendation? Check out the Elixir Mix!