DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Byte Sized
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! ๐Ÿ˜‚

excited.gif


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.

carbon_2830_29.png

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.

line.gif

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

Now, letโ€™s create a list:

carbon_2847_29.png

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

carbon_2841_29.png

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.

carbon_2832_29.png

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.

carbon_2842_29.png

Finding a node

books.gif

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.

carbon_2833_29.png

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:

carbon_2834_29.png

Removing the node

wheres-my-book-cannot-find-it-still.gif

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

carbon_2837_29.png

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.

carbon_2845_29.png

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:

carbon_2836_29.png

As a bonus, hereโ€™s this question from leetcode. Weโ€™ll solve it, but with a twist. ๐Ÿค” Can you spot the error?

carbon_2846_29.png

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?

Top comments (0)

Let's team up together ๐Ÿค

We're Hiring

We're hiring for a Senior Full Stack Engineer to join the DEV team. Want the deets? Head here to learn more about who we're looking for.