In this blog I will be talking about linked lists. It is a data structure that comes up often in algorithms and computer science. I will talk about the structure of linked lists and how they work as well as going through an example of a common linked list algorithm which will hopefully tell the reader a bit more about how to play with linked lists.
So linked lists are a common data structure within computer science and programming. You might hear it come up along with graphs or trees. Linked lists are a linear structure that are made up of what are called nodes. The way I describe nodes to people is fairly simple. They are almost like an arrow, and this arrow has a value and also a next. This arrows value is fairly self explanatory but the next is also an essential part of the node itself. It points to (in a linked list) the single next node which will also have a value and a next. So in a way its almost as if node 1 has a value of blah and a next which is node 2's value of blah blah. A picture representation might help here :
This is a visual representation of a linked list. The first node has a value of 4 and a next of the following node which has a value of 5 and so on. The obvious question that you may be asking yourself here is how do we deal with the first and last node? Well for starters the last node will always point to null. Now sometimes there is not a last node. In this case the last node's next would point the the first node. In a linked list like the one above, we generally refer to the first node as the head.
Ok now traversing through a linked list is not too bad. Generally we will have a problem such as removing elements (nodes) from a linked list. In the example I am providing we will be provided the arguments of a head and a val that we are trying to remove from the list. The first thing we will want to do is assign placeholders for the current node we are checking and the previous node.
We assign the current to head because we are going to start our search at the head. We assign the previous to null because in our current linked list there is a head and a tail, meaning the linked list will have an end, like in the first picture. The way we get rid of a node is quite simple, yet maybe not the most obvious answer. Essentially we skip it. Let me explain more.
We described a node earlier as a sort of arrow thing that has a value and a next. If there is no other node attached to said node then it is no longer a part of a list. So in order to move through a linked list what we can do is make a while loop that checks our current node value. If it is not what we want we can change it by changing its next value. Or we can remove it (if it is the one we want to remove) by changing the previous nodes next to the currents next.
So look at this code. Our while loop will break once we have removed all the values in the list that we don't want. As we move down the code we check if the value of the current node we are checking is the val that we want to eliminate. Then we have to check if the previous node is null because that would mean that the head is one of the values we want to get rid of. If that is the case, we can right off the bat change the head to the next node which will eliminate the previous head. Otherwise if the current node we are checking is the value we want to eliminate, we will just change the previous to our current's next which would eliminate the current node we were checking.
Otherwise we just move through the list. How we do that is just by making the placeholder for our previous node = to the current node and then making the current node = the next node. Using this process we will eventually go through all the nodes and remove the ones that have a value that we are looking for. We use the placeholder of current rather then the actual head because at the end in order to return the new list we need to return the head, which will be the head of a mutated list that we have just changed by removing certain elements. You might remember previously that we change the actual head if the first node in the list happens to have the element that we are trying to eliminate, that is because we obviously wont want that head anymore and we want to actually change the head to the next node. Thanks for reading.
Top comments (0)