For the first time in a long time, I finally started to understand linked lists. I had been looking at this data structure on endless forums and youtube videos trying to explain what it was by some kind of diagram that looked like this:
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
}
Now obviously, this is a very small portion of the code which I found on GeeksforGeeks, and I'm sure that if I took a look at it now I would understand it, but this tells me little to nothing, if I'm not able to connect the dots with the rest of the code. The thing about linked lists is that it is a very abstract concept, and without actually coding out your own, you are very likely to get lost when the methods juggle with a lot of moving parts.
Before I dive in, I want to give credit where it's due: my breakthrough came because of the 'Mastering the Coding Interview: Data Structures' by Andrei Neagoie, who I think many of you might already be familiar with. His methodical pace and his hands on approach to learning was what really pushed me to finally code out my own linked lists along with their methods. If you haven't already taken his course I highly recommend it.
With that, as an overview, I want to go over briefly the class constructor methods necessary for a linked list, and then some of the methods I coded as I followed along in the course. I did amend part of these answers after seeing the solution, but I did attempt the solutions myself at first. I will try to share insights I received from both portions of the lesson, and clarify issues others might be having.
First things first, what does a linked list consist of? Well, as the name suggests (and as I originally expected) a list of what are usually called nodes, which is an object which holds a value, and a next node attribute. This is contained inside a linked list object itself, which has attributes that keep track of the head, the tail and the length. This indicates the need for two generated objects or two classes, one for the node and the other for the linked list itself. Something like this:
class LinkedList{
constructor(value){
this.head = {
value: value,
next: null
}
this.tail = this.head
this.length = 1
}
class Node{
constructor(value){
this.value = value,
this.next = null
}
}
As some of you might have noticed this differs a bit from the first example in that we initiate the head attribute with a node inside of it. First of all, this structure initiates the class with the node already in place. Although it might be bad to do this because you might want to initialize the linked list without a node in it to begin with, I personally felt like it made it easier to visualize what we're working with. We are setting this.head to refer to a specific node, which is the one we intialized it with. Secondly, this class used a this.tail class which was initialized to equal to the head node. Similar to how it was easy to see what the head was, when we also initialized the tail attribute as equal to the head, I could make sense that, ok, this attribute essentially equaled the only and 'last' node in the linked list.
Now to move onto some methods. How would add something to the linked list? Let's think again about what we're working with. We're adding a node, so we have to 1) account for that node and it's value, 2) the current tail's next node value being changed to the new node, 3) the change in the tail's position, and 4) the change in the length of the linked list.
append(value){
var newNode = new Node(value)
this.tail.next = newNode
this.tail = newNode
this.length++
// return this
}
This is the code exactly in that sequence. Since append only ever deals with the adding something to the end of a list, we never have to touch the head. In the case that it's the first append, we wouldKeep in mind the first line is just utilizing the constructor function we created before. Also, it's important that we did the 2nd step before the 3rd one, because if they were flipped, the new node's next attribute would end up pointing back to the head node, instead of it being the other way around.
Having done the append, the prepend method should be pretty easy to deal with. We still have to create a new node, but since we are adding this to the beginning of the class, we just need to do the opposite in terms of assigning the next variable, and make the new node's next variable the current head, and then switch the head. Again, doing this in that order allows us to not lose the head class. This is our result.
prepend(value){
var newNode = new Node(value)
newNode.next = this.head
newNode = this.head
this.length++
//return this
}
Now inserting is a little bit trickier, because whereas we don't have to reassign the this.head or this.tail attribute from the linked list, we do have to deal with changing the next attribute of both the node in the index previous to where we want to insert and the new node's next attribute. The reason we need to set the next attribute of the index before the spot we want to insert, is because whatever index the user selected to place this node is then going to be one after that. To help visualize this better, here's a diagram of everything that's happening during an insert. In the diagram, the cursor would be the index one before to the insert spot which I was referring to.
To implement this, here was the code that I used.
insert(index, value){
if(index <= 0){
return 'use prepend method'
} else if(index > this.length){
return 'use append method'
}
var newNode = new Node(value)
var holdingPointer = this.traverseToIndex(index - 1)
var nextPointer = holdingPointer.next
holdingPointer.next = newNode
newNode.next = nextPointer
this.length++
//return this
}
traverseToIndex(index){
let counter = 0
let currentNode = this.head
while(counter !== index){
currentNode = currentNode.next
counter++
}
return currentNode
}
Couple points worth mentioning is that first of all, I checked the input for whether it equaled 0 or something equal to or greater than the length of the array. If the user was trying to add something to those indexes, it would actually return an error, since the insert method deals with grabbing nodes before and after that index, and the first index doesn't have a previous node, and the last index doesn't have a next node. The error messages point them to the append and prepend methods which do what they are looking for in those cases.
Also the other notable thing is that I ended up using a traverse to index that would get us to the index we are looking for in a separate function. Technically I could have just used index - 1 in the function and not separated it, but this allows for less clutter and separation of responsibilities, something I'm starting to find as essential in writing readable code.
Now to run through the solution, we get the node before our insert location along with the node after it and our new node. With three nodes at hand, we can now take the first node and make it's next attribute equal to the new node, and the new node's attribute to the third node. This accomplishes the method displayed in red arrows in our diagram. Finally we increase the length by 1.
Last but not least is the delete method. Here is the first method where we actually dont have to create a new node, but we simply reassign our next attributes. When we isolate a node by doing this, it actually gets disposed of by the engine's data disposal and don't have to manually delete it. Here's the code.
delete(index){
if(index == 0){
const leader = this.traverseToIndex(0)
this.head = leader.next
leader.next = null
} else if(index >= this.length - 1){
index = this.length - 1
this.tail = this.traverseToIndex(index - 1)
this.tail.next = null
} else{
const leader = this.traverseToIndex(index - 1)
const connectingNode = leader.next.next;
leader.next = connectingNode
}
this.length--
//return this
}
Again, I checked the inputs, but because there's no other method that takes care of deleting nodes, I ended up writing functions that adjusted the indexes and assigned the next values to null to cut off the relationship with those end nodes. In the case where the user called for a node in the middle, I went the node before the removal spot, and connected that with the node that was two spots after it. This left the unwanted node unconnected and was deleted.
Having gone through step by step, it's probably important to talk a bit about time complexity here, since this is pretty much the reason we should consider different data structures. The time complexity of searching in a linked list is 0(n) for searching and O(1) for insertion in comparison to the opposite, which is an array that has O(n) time complexity for insertion and O(1) for searching. This means a linked list is useful for situations where you do have to keep adding new pieces of data, because you don't have to restructure the entire data structure when you do so like an array.
If order is not an issue for you (something that arrays which are ordered/indexed list is good at), linked list is the data structure for you. Do mind though, when we implemented our insert methods which do look for specific indices, which means we are taking order into account, we ended up looping through and searching the linked list, before we performed the O(1) insert operation. So the advantages of linked list in adding and removing is only in relation to doing this to the end and the beginning of a linked list.
Learning about linked lists, their methods, and why they are important are vital in passing coding interviews where they test your understanding of data structures and algorithms, but looking at mere solutions was not doing it for me. If I could add just one last thing, actually coding out solutions for concepts you are learning, I've learned that it is absolutely vital in internalizing conceptual matters. I hope you learned something, and that you can also put this extremely effective method of coding alongside programming concepts you read about.
Top comments (0)