In this series of articles we go through the fundamentals of different concepts, algorithms and data structures in the prism of JavaScript. Computer Science has long been a topic neglected by JS developers because of it’s inapplicability in modern development.
We have the basic problems solved for us out of the box and we would never have to implement our own basic algorithms. However, the proper understanding of those concepts really does improve us. Not in our knowledge of JavaScript but our general understanding of software development.
In this article we will look at linked lists — what are they used for and how we can implement one.
Some theoretical knowledge
First, what is a linked list. This is a data structure which will store different values and is often compared to arrays. They both serve the same purpose — store some data, but the difference is how they actually store it.
An array usually has fixed size and a defined type of data that it will store. This allows it to take consecutive pieces of memory which it will use to store the values that we give it.
A linked list on the other hand has no fixed size. We add elements to it one by one and every element is responsible for pointing to the next one. Therefore the values that we pass will reside in different places in memory and depend on the items in the list to point to the next one.
Another difference is the performance of operations in the two data structures. Arrays have a constant time when it comes to accessing elements. This means that taking the first element of an array will be the same as taking the 100th one. This is because of the way that the elements are stored in memory.
In linked lists, on the other hand, accessing an element requires you to run through the items of the list and check each one if you have found it. In the worst case you will have to iterate through the whole list, which is quite slower than the arrays.
Another common operation that we apply to such structures is the adding and removing of elements. Arrays tend to be quite slow here, because of their static nature. They have a fixed amount of memory that they keep and adding a new item usually requires the whole array to be copied while allocating more memory. Now, imagine adding an element in a particular location in the middle of the array and what kind of shuffling this would cause. Removing an element is available but in reality you only nullify the value. The memory is still being reserved for the array.
Linked lists are more performant in this situation. Adding an element anywhere in the list will require only a change of pointers. Removing is also a fast operation which will also free up the memory allocated for the particular element. If there are no references to it it will be garbage collected.
Implementing a linked list
Before we start with the implementation there are some things to note. There are multiple types of linked lists and more than one way of implementing them.
We will implement the most basic linked list. It will consist of nodes and every note will have a pointer to the next one. The last node in the list will point to null, which is useful when we are iterating through it and want to know when to stop.
Before we start I want to say that there are probably better implementations than what I will show you here. For the sake of the article the logic of the linked list and it’s operations will be described as thoroughly as possible.
The length property is used to keep track of the size of the list without having to iterate through it every time we need it. The head is the first item in the list and we will be using it as a starting point when we are iterating through the data structure.
The first piece of logic to implement will be the add method. Whenever we try to add an item to the list, it will go through the list, find the last node in it and add the new item after it. The only special case here is when the list is still empty.
A possible pitfall here is to forget to increment the length property which will lead to a new head pointer being set every time.
I mentioned how fast linked lists were when it came to adding elements, but this method of adding will force us to loop once through the list every time we want to append another node to it.
Another approach is to add the element as a first item to the list, add it as a new head and have it point to the former head element. This functionality will always require the same number of steps no matter the size of the data structure.
We can now add elements to our linked list, hurray! Of course, some times we make mistakes when appending nodes and we will want to fix them by removing an element. This is also pretty straight forward once you wrap your head around it.
We will delete an element by it’s value. So first we need to find the element that we want to remove, it may be somewhere in the middle of the list. If we just remove it or set it to null it will break the link to the elements after it, so we must think of something else.
What we will do instead is to iterate through the list and check every element if it’s the one we’re searching for. Meanwhile we will also keep track of the previous element that we’ve tested.
So when we find the node we’re looking for we will just set the previous node’s next pointer to point to the current one’s next pointer. This way the node we want to delete will have no references to it and will be garbage collected.
Things to pay attention to is the case in which the node to remove is the head. Also remember to mutate the length property.
If you need to find whether a node with a particular value is in the list you can use the logic we’ve written in the remove method.
Other kinds of linked lists
The doubly linked list is a data structure which is similar to the normal linked list with the difference that each node keeps a pointer to the next node and previous one. This can be useful when we want to go backwards not only forward through the list.
The circular linked list is a list in which the last node’s next pointer points to the first node of the list, Thus creating a circular structure. This can be useful because it allows us to iterate through the whole list even if we don’t do it from the start, but it can also be quite tricky.
What’s next?
I hope this article helped you understand the fundamentals of the linked list data structure. You can help me out by holding the clap button and sharing this article with friends!