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 . Check it out, and try to solve your challenges too! here 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! , remove the k-th node from the end of the list and return the head of the list. Given a linked list and an integer k is guaranteed to be smaller than the length of the list. k 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 to remove from the list. After that, we should return the head of the linked list. k 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 is by the list, so we don’t have to check for it to go beyond the actual length of the list. k contained 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 ), and each node must have at least two properties: a (something actually contained by the node) and a to the next node. nodes value link Usually, a is used as a link to jump from one node to another. pointer Also, the first node of the list is usually called the of the list, which is also the node we are asked to return by the problem. head 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 which redirects the list to the next node The following node will contain its value and a pointer to the next node, and so on. P(n₁) n₁. n₁ P(n₂) 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! https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true 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 and the property , which holds a type as a pointer to the next node. Value Next *Node The linked list, a structure to “initialize” the linked list, which will only have one property, the of the list. Head 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 which will contain the next node. This last node then will have his property to jump on the next node, and so on. the Head node, since is of type Node , will inherently have a Next property, Next 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 tedious job, or we write a method for the linked list class to add some more nodes. Let’s check it out! really 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 and lists. mutable immutable As their names suggest, . Immutables, instead, have a with new elements. But why is it so? mutable lists are lists that you can manipulate and add elements to fixed size and cannot be appended Immutable lists are , meaning that their elements are : 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. contiguous in memory stored in memory sequentially 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? , which will bring us the to element appended, and so on. Well, because the last element of the first initiation will have a pointer that the element added after it So yes, mutable lists are really often linked lists in disguise! Now, let’s see the code: https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true We added the method to the methods of our linked list. The process to add a node goes like this: AddNode First, we store the value in a variable called Head current Next, we loop over the linked list updating the variable with the next node every time, until the next node is null. current 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 pointer of this new node will be set as null if we leave it blank) Next 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, , right? a node in a linked list only exists if it’s connected to the previous one For example, if we give the n-1ᵗʰ a value of null, we can disconnect the nᵗʰ value from the list. Next 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, : try something like 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. we can not index directly the list linkedlist[n] What we can do then is implement a to keep track of the node we are on! counter Let’s code it then. https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true Let’s look at the function which accepts an attribute. After that, we initialize three variables: RemoveNode index , which will hold the previous node previousNode , which will hold the node we are on during the loop current , initially equal to 0, which will hold our position on the list counter Let’s skip the first if block for the moment and concentrate on the for loop instead. We start looping until our variable is strictly smaller than our : each loop will then counter index update the previous node with the current one and move on to updating the current node and the counter. it means that When the loop breaks, 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 and , and the condition would be instantly false. We can manage this first case with the if block at the top. counter = 0 index = 0 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, , meaning that the function retains a of the passed object, . passes the attributes to the functions by value copy 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 is created just with the purpose of passing it to the function. a 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 and , and we can check for the result where node 0 and node 2 will be missing. ll.RemoveNode(0) ll.RemoveNode(2) 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

Too Long; Didn't Read

Making security fun one episode at a time

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

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

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

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES