Beginner’s Guide to the Linked List Data Structure in Nodejs
Before you learn about the why, how, and when to use a linked list data structure for your project it is crucial to conceptualize how a linked list works.
What is a Linked List?
A linked list is a linear data structure stored randomly in memory and is made up of nodes that contain a value and a pointer.
So, a linked list is a linear data structure. This means that the data is “chained” one after the other in a linear fashion. Think of it like you are waiting in line; people exist one after another. When you approach a line you know who is first and last in line by identifying that there are no people behind/in front of them, while every other person has one in front and one behind. Similarly, a linked list or any other linear data structure keeps its data in order one after another.
You are probably thinking that a linked list is similar to an array. You would be right to make this assumption because they both use a linear data structure to organize data. But they are different because in a linked list the data is stored randomly in memory while the data in an array is stored together. For programmers, this means all of the data in an array can be accessed from a single reference in memory. In simpler terms, this means that the computer program only has to find the start of the array and it knows that for every x bytes (dependant on the data type) the next value will follow until it finds the end of the array. JavaScript knows by checking the length of the array when the array is declared. Linked lists do not use this strategy. Instead, when a linked list is called, JavaScript points to the head, and the rest of the data is scattered in memory, through the use of pointers within each node, the sum of data is still stored linearly.
Let’s dive into what exactly is a node. As you know a node is a “container” which holds two pieces of data; a value and a pointer. A node is a custom data type that you must define for a linked list, and in the definition, you must include two variables: one for the value which can be any data type in JavaScript, and one for the pointer to the next node.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}The code above is the blueprint for a node in JavaScript. When you create an instance of a Node you pass in the value and the node which follows it. Declaring a next method in the node allows you to create instances of Node whenever you want throughout the duration of your program. This also allows you to maintain a linear order as each node tells JavaScript where to look next, and when next is null, JavaScript will know that it has reached the end of the list. Earlier we thought of a linked list as a line, now we know that’s not accurate with how nodes are stored in memory. Instead, we can think of a linked list as a Take-A-Number system. This is a more accurate description of a linked list. The Take-A-Number system can be visualized as if you had walked into a waiting room and saw people waiting around in a scattered fashion; you grab a number and wait for your number to be called. As you see the next numbers pass, people stand up from different spots with no pattern. This is how a linked list is stored and used.
Why Should I Use a Linked List?
Here I am going to discuss what makes a linked list good and what makes it bad in comparison to the array data structure.
As developers, we judge the quality of a data structure based on three characteristics: the speed it takes to search, insert, and remove elements from it. More specifically, we calculate the Big O notation of each of the categories.
A linked list is best used when your task will frequently insert items from its list. For the insertion method, a linked list is O(1) in its worst case, which is as fast as possible. On the other hand, an array performs an insertion in O(n) in the best and worst-case scenarios. Arrays are statically declared, meaning that you get 1 shot to add everything you want and put it in the right order. Any time you want to add to it, the array must be remade so that all of the values can exist next to each other in memory.
Now if you have worked with arrays before, you know how fast it is to find a point of data with indexing O(1). Searching is the area where linked lists aren’t so great and if your task is going to do a lot of searching, you likely do not want to use it as your data structure. A linked list will have to start at the head (start) of the data and go to each Node until it finds what it’s looking for. At its best, a linked list will perform this in O(1). At its worst, it will have to check every Node and find what it’s looking for in the last one; performing the task in O(n). Both of these situations are very unlikely, with a 1/n chance of occurring for each of the two scenarios. The most common outcome will be somewhere in the middle of the data which would be around O(n/2) and rounded to O(n) … not great.
Lastly, there is the deletion method which is not a highlight for either of the two data structures. Linked Lists perform deletion in O(n) because it has to search through each Node one at a time which is the same reasoning as the searching method. Meanwhile, arrays also perform at O(n) as arrays need to be reformed every time as mentioned in the insertion paragraph. Linked lists aren’t great for deletion but are on par with array’s in this category so it should not be a reason to choose a linked list over an array.
Consider using a linked list data structure if you are going to perform many insertion tasks or if you will not be able to leverage the index search in an array.
How to Build a Linked List in Javascript
This guide will assume you have prior knowledge of object-oriented programming. Keep in mind that this will not be the only way to use and create a linked list; you may build it in a slightly different way or add more methods as you see fit.
The first step is to create a Node class as seen above.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}Next, you need to create a LinkedList class.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}Here we are declaring the structure of a LinkedList and Node so that instances can be made from them. However instances of these two classes can’t work together yet, so let’s add more methods!
First, let’s allow for the creation of the first Node within the LinkedList class.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Insert head aka first node
insertHead(data) {
this.head = new Node(data, this.head);
size++;
}
}
const ll = new LinkedList();
ll.insertHead(3);
console.log(ll) //Outputs: {head: Node {data: 100, next: null},
//size: 1}Let’s break this down. I created a new method insertHead which creates an instance of Node within the LinkedList and assigns it to the head. When called we get an object which contains the head. The head is the Node we created with the value of 13 and no next since there was no head before the creation of this Node. Following the Node, we see the size which is 0 … odd? Nope, this is a class we made ourselves so we will have to remember to increment the size each time it grows.
Now if we were to continue with the code written here and call ll.insertHead(100) another time we would see.
{head: Node {data: 100, next: Node {data:13 next:null}}, size: 0}The insertHead method properly makes the previous head become the next (pointer) to the newly created head.
Now you have to be saying “I’m sorry linked list you sound cool but you’re kind of ugly to read. How will I ever debug you?”. Well, that’s ok because we can fix that with a new method to only print the data of each node.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Insert head aka first node
insertHead(data) {
this.head = new Node(data, this.head);
this.size++
}
//Pretty print of data
printData() {
let current = this.head;
while(current) {
console.log(current.data);
current = current.next;
}
}
}
ll.insertHead(2)
ll.insertHead(1)
ll.printData() //Outputs: 1,2Now when we call the print data method we will only get the values. Much better.
Remember that the first and last nodes in a linked list are different from the rest. We already have the method for the first; let’s make the last.
//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Make a Node at the end
insertLast(data) {
let last = new Node(data);
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
this.size++;
}In the insertLast method, we are creating a new Node and keeping it in the variable last. We then make a pointer to the head and create a while loop going through all of the next nodes like a chain while next is not null. When next is null we know we are at the end and then assign the currently last Node’s next method to point at the newly made node in the last variable.
Next is to show how to insert a Node at any other place in the linked list.
//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Insert node at index
insertAt(data, index) {
const node = new Node(data);
let previous;
let current = this.head;
let count = 0;while(count < index) {
previous = current;
count++;
current = current.next;
}
node.next = current;
previous.next = node;
this.size++;
}
}
This one is where people get confused in linked lists so refer to the graphic above to make sense out of it as you read.
In the insertAt method, 2 parameters are taken but only the index is new. With the index, you can specify where in the linked list you want the new Node to be placed. First, we assign the new Node inside the node variable. We need to declare an empty previous variable. We have to start every search from the head of the linked list so we make a reference to the head and store it in the current variable. The last variable we need to make is count which is initialized to 0; this will be used to count up to the index argument.
Inside of the while loop, we are doing what you have seen before which is searching through the linked list. However, there is a difference, now we are incrementing count each loop and stopping after count is equal to the index argument. In the image above this is like searching until JavaScript finds the 3rd Node at index 2. When the loop is finished we will have the previous node in the variable previous and the node currently at the index, node needs to take in the variable current. We then replace the next connection between the previous (B in the graphic) and point it to node (E in the graphic). The linked list would end at node if we stopped here because it doesn’t point to anything. We then make the next of node point to next (C in the graphic).
There you go! We can now insert a new Node at any point in the linked list. Now all that’s left is to make a search and delete method.
//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
//return the data at index
search(index) {
let count = 0;
let current = this.head;
let foundData;
while(current) {
if (count === index) {
foundData = current.data;
}
count++;
current = current.next
}
return foundData;
}
}Here I created a method to return the data at the index of the argument passed into the search method. You have seen a lot of it before so I will touch on what’s new. We are declaring an empty foundData variable and looping through the list until count is equal to the index argument then storing the data of the Node at that location inside the foundData variable. Then we simply return the foundData variable and that’s it! The rest are all things you have learned already.
Lastly, we need to be able to delete a Node from the linked list.
//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Remove at index
remove(index) {
let current = this.head;
let previous;
let count = 0;
if(index === 0) {
this.head = current.next;
} else {
while (count > index) {
count++;
previous = current;
current = current.next;
}
previous.next = current.next
}
this.size--;
}
}By now you can probably understand what’s happening here. Everything in the code above is a mixture of other things you have learned. Here’s a quick recap of what’s going on.
The remove method can be called and passed an argument which will be the index of the Node to be deleted. If the index was 0 it needs to be handled differently because there isn’t a Node behind it. If the index is 0 we simply need to store the second Node inside of the head. That’s done, now what if it’s not the first? Then we loop through the list while count is less than the index argument. When the loop finishes we have the current + 1 inside current and previous Node’s. We then attach the two by changing the next of previous to point at current.
DONE! That’s all the basics of how to make and use a linked list. You will want to add more methods and build on the current methods as they are barebone and provide no error checking.
Doubly Linked Lists
Yes, there’s more. This will be quick to understand with all of your amazing knowledge on linked lists.
There is another type of linked list called a doubly linked list. It is much less common than a linked list, but it has its place. Its name is very fitting and it is the same thing as a regular linked list but it has 2 pointers (links) one forward and one back.
As you can see it looks the same. Except there are 2 pointers for each and 2 null’s one in the front and one in the back.
This type of linked list has a very niche use. You’ll find it useful when you are creating a feature that needs to undo and redo. Think of your web browser, it has a forward and previous button. This can be done with a doubly-linked list, but not a regular one. If you were to click on 3 websites, then go back 1 step, then go to another different one you wouldn’t be able to access the 3rd website through the forward and previous buttons. This is because the link has been broken and is now attached to the last website you went to. Similar to how we inserted a new Node except the next on the last website you visited is null since it is the most recent.
