In JavaScript, adding elements to an array is not efficient, compared to other programming languages such as c/c++. In such cases where operations performed on arrays are too slow for practical use, linked lists may offer a better solution.
What are Linked Lists?
A linked list is a collection of objects, which are linked together. We call these objects, nodes. An example linked list would look like the following.
Each "Item" represents a node, and the arrows represents the link between the nodes. The "null" node is there to indicate the end of the list.
Sometimes, we will have a node called the "head" as the first node. It is not necessary to have a head node, but it is used to indicate the beginning of the linked list.
Creating a Node
A node is simply a JavaScript object. Let's use a constructor function to create our nodes.
function Node(value){
this.value = value;
this.next = null;
}
The "this.value" is the data we want to store in the node. "this.next" is used to link to the next node.
Let's create a node using the constructor function and output the value.
let dummy_node = new Node('Item 1');
console.log(dummy_node.value);
Creating a linked list from nodes
It is important to node that when creating a linked list, we are not creating a lot of separate nodes. We create one main node, then we add new nodes to that node. Let's look at an example.
So far, our code should look like this.
function Node(value){
this.value = value;
this.next = null;
}
let dummy_node = new Node('Item 1');
Our "dummy_node" itself is a linked list. We just need to add more nodes to it. Here's how we do that.
function Node(value){
this.value = value;
this.next = null;
}
let dummy_node = new Node('Item 1');
// Adding new nodes
dummy_node.next = new Node('Item 2');
dummy_node.next.next = new Node('Item 3');
dummy_node.next.next.next = new Node('Item 4');
If we want to print out the values, we can do it like this.
..
console.log(dummy_node.value);
console.log(dummy_node.next.value);
console.log(dummy_node.next.next.value);
console.log(dummy_node.next.next.next.value);
As you can see, this is not the most convenient way to inserting and retrieving our data. So, let's create a function to add new elements.
function add(value){
let position = this;
while(position.next != null){
position = position.next;
}
position.next = new Node(value);
}
We need to update our "Node" constructor function as well.
function Node(value){
this.value = value;
this.next = null;
this.add = add;
}
Our complete code should look like this:
function Node(value){
this.value = value;
this.next = null;
this.add = add;
}
function add(value){
let position = this;
while(position.next != null){
position = position.next;
}
position.next = new Node(value);
}
Now let's create our linked list and add items to it.
let L_List = new Node('item 1');
L_List.add('Item 2');
L_List.add('Item 3');
Now it's more convenient for us to add values to it. How about printing out the values inside the list? Let's create a function for it as well.
function print(){
let position = this;
while(position != null){
console.log(position.value);
position = position.next;
}
}
Just like before, we need to update the "Node" constructor function.
function Node(value){
this.value = value;
this.next = null;
this.add = add;
this.print = print;
}
Our full code should look like this:
function Node(value){
this.value = value;
this.next = null;
this.add = add;
this.print = print;
}
function add(value){
let position = this;
while(position.next != null){
position = position.next;
}
position.next = new Node(value);
}
function print(){
let position = this;
while(position != null){
console.log(position.value);
position = position.next;
}
}
let L_List = new Node('item 1');
L_List.add('Item 2');
L_List.add('Item 3');
Now, let's print the values in our linked list.
L_List.print();
These are some of the basic things you need to know when working with linked lists. To improve your understanding further, try implementing this on your own. Also, I recommend trying out some leetcode problems that are freely available(not sponsored by them).
Also, consider subscribing to my newsletter to stay updated when I post new content.