Byte Sized

Posted on

# 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/