Daily Coding Problem: Remove the k-th Index From the Linked List in One Pass

Removing k-th Index From Linked List in One Pass

Welcome back, with another problem to solve! Today, we are dealing with linked lists and their elements removal. We’ll discuss a bit about what linked lists are, we’ll create one, and see how to remove elements from it.

Before starting, the usual disclaimers:

• These problems are provided by the wonderful newsletter Daily Coding Problem, which you can subscribe to here. Check it out, and try to solve your challenges too!

• I’m not an expert programmer: Just a guy who likes to share his shots! If you happen to have a better or faster solution for an algorithm, please submit it in the comments! I’d love to learn some more about this!

  
  

Enough ado; let’s jump to the problem!

Given a linked list and an integer k, remove the k-th node from the end of the list and return the head of the list.

k is guaranteed to be smaller than the length of the list.

Do this in one pass.

Alright then, let’s explain a bit what’s happening here: we are given a linked list and an index element k to remove from the list. After that, we should return the head of the linked list.

Finally, we must do all of this in just one pass, meaning that we can not loop over the list more than once.

We are also guaranteed that the index k is contained by the list, so we don’t have to check for it to go beyond the actual length of the list.

We will use Go to build the algorithm today since its syntax is awesome for this kind of job, and at the same time, it remains pretty simple to understand.

Let’s start from the beginning: building a simple linked list.

The Linked List

The concept behind the linked list is pretty simple: it’s a list made of objects (usually called nodes), and each node must have at least two properties: a value (something actually contained by the node) and a link to the next node.

Usually, a pointer is used as a link to jump from one node to another.

Also, the first node of the list is usually called the head of the list, which is also the node we are asked to return by the problem.

Here’s a graphical example:

The first node on the left is the head of the list, which contains its value v₀ and a memory pointer P(n₁) which redirects the list to the next node n₁. The following node n₁ will contain its value and a pointer P(n₂) to the next node, and so on.

The final node, of course, will have nothing to point to, so the value of its pointer will be null.

Let’s see the code to create one!

The code is pretty simple: we create two structures, one for the inner node and one for the linked list.

• The node, as we have just seen, will have two properties, namely the property Value and the property Next , which holds a *Node type as a pointer to the next node.

• The linked list, a structure to “initialize” the linked list, which will only have one property, the Head of the list.

  
  

After that, we simply initialize the list in the main function and give its head a node with a random value of 10.

The key behind understanding the linked list is that now the Head node, since is of type Node , will inherently have a Next property, which will contain the next node. This last node then will have his Next property to jump on the next node, and so on.

Everything will be more clear once we add some nodes to the list, so let’s do it! We have two options: either we do it manually, a really tedious job, or we write a method for the linked list class to add some more nodes. Let’s check it out!

Adding Nodes: Mutable List in Disguise

Even if you have little programming experience, in almost every programming language, one of the first concepts you should have heard about is the difference between mutable and immutable lists.

As their names suggest, mutable lists are lists that you can manipulate and add elements to. Immutables, instead, have a fixed size and cannot be appended with new elements. But why is it so?

Immutable lists are contiguous in memory, meaning that their elements are stored in memory sequentially: for a list of 3 elements, if the first element is stored at 0x00, then the second will be at 0x01 and the last at 0x02.

That’s why it is so fast to iterate over a fixed array, an immutable list, or a tuple in Python because the CPU simply recalls memory indexes one by one.

On the other hand, mutable lists are contiguous in memory only when first initialized: at that point, if elements are added, they will be not sequential anymore. So how can we loop over them?

Well, because the last element of the first initiation will have a pointer that the element added after it, which will bring us the to element appended, and so on. So yes, mutable lists are really often linked lists in disguise!

Now, let’s see the code:

We added the method AddNode to the methods of our linked list. The process to add a node goes like this:

• First, we store the Head value in a variable called current

• Next, we loop over the linked list updating the current variable with the next node every time, until the next node is null. Once the node we are currently on has a null pointer, we know that we are on the last node of the list.

• Lastly, we update this last node with a new node and a new value (the Next pointer of this new node will be set as null if we leave it blank)

  
  

Graphically, this process is something like this:

We can check the correct functioning of this method in the main function, printing out the values of the nodes in the linked list.

Removing the Node

Now for the final part and solution to our problem: removing a node with the correct index. First off, what does it mean to remove a node from a linked list? If we think about it, a node in a linked list only exists if it’s connected to the previous one, right?

For example, if we give the n-1ᵗʰ a Next value of null, we can disconnect the nᵗʰ value from the list.

What if the element we want to remove is not the last one? Well, we can unlink the element by connecting the previous one to the next one of it!

So to remove the kᵗʰ element, we must find the k-1ᵗʰ element and link it to the k+1ᵗʰ node. We will need to store the previous node (k-1ᵗʰ).

Obviously, we can not index directly the list: try something like linkedlist[n] will just raise up an error. Given this though, we can consider the head of the list as index 0, and its next node as index 1, and so on, and we can also loop over the nodes, as we’ve done before.

What we can do then is implement a counter to keep track of the node we are on!

Let’s code it then.

Let’s look at the RemoveNode function which accepts an index attribute. After that, we initialize three variables:

• previousNode , which will hold the previous node

• current , which will hold the node we are on during the loop

• counter , initially equal to 0, which will hold our position on the list

  
  

Let’s skip the first if block for the moment and concentrate on the for loop instead. We start looping until our counter variable is strictly smaller than our index : each loop will then update the previous node with the current one and move on to updating the current node and the counter.

When the loop breaks, it means that we are just on the node before our desired index: we just need to update the pointer of the previous node, prev.Next , with the next node in the list from this one we are on, which will be current.Next . Finally, we return the head of the linked list.

Now what happens if the index to remove is the head, which has an index of 0? The loop would never start because it will start with counter = 0 and index = 0, and the condition would be instantly false. We can manage this first case with the if block at the top.

Basically, if the index is 0, we can directly update the head of the linked list with the node next to it, and return it. I’d like to point your attention, particularly to line 31: Go, as in many other languages, passes the attributes to the functions by value, meaning that the function retains a copy of the passed object, not the actual object you are passing.

This concept is clearly seen in this example:

package main
import "fmt"

func printMemoryAddress(value int) {
 fmt.Println(&value)
}

func main() {
 a := 10
 fmt.Println(&a)
 printMemoryAddress(a)
}

// 0xc00010a000
// 0xc00010a008
// Program exited.

We create a function to print the memory address of the value passed as an attribute. Then, in the main function, we create a variable a and print out its memory address. Then we pass the same variable to the function and print its memory address.

As you can see, if you try, the results will be different: that is because attributes are passed to the functions as value, meaning that a copy of a is created just with the purpose of passing it to the function.

Back to our linked list, we must use pointers to get the real head for the same problem above. So to get to the “real” ll.Node we must recall it’s pointer, *ll.Node and move it further with *ll.Node = *ll.Node.Next .

In the main function, we add the calls to the method, for example, calling ll.RemoveNode(0) and ll.RemoveNode(2), and we can check for the result where node 0 and node 2 will be missing.

Conclusion

We’ve made it to the end!

If you read up to this point, my whole gratitude goes to you. If you are willing to leave a like or two and share the article, it will make my day and help me continue writing these articles!

See you in the next article, and, as always, thanks for reading.

Nicola