Introduction
The linked list is one of the most popular linear data structures!
But wait, linear, how?
- By definition, a linear data structure arranges its elements in a linear fashion, where one element is connected to the next and previous element. When we started learning the program, we all came across arrays; Arrays are the best example of linear data structure; they store elements index-wise in a linear trend. But arrays have some limitations, one of them being a fixed size. This can be solved with LinkedList.
So basically, LinkedList is a list of nodes, but now what on earth is a node?
- Well, the node is a user-defined class that holds 2 properties. The first property is the value to be stored, and the second is the pointer to the next node; as you can see in Image 1 below, we have a node with a value of 10, and it's pointing to node 2.
Image 1- Single Node in a LinkedList
What are we going to learn in this article?
- How to create a node
- How to create a LinkedList class with a head node
- Print LinkedList
- Add tail node
- Add a new head node
- Inserting a node in between a LinkedList
- How to delete a head node
- Delete a tail node
- Delete a node by index
- Delete a node by value
- Search an element in the LinkedList
1. Create a Node
Listing 1 shows how to create a Node class in JavaScript. Create a class Node, which will take value in a constructor and create 2 properties: value and next; next is the pointer which will get assigned as we code ahead. For now, let's say it's null, we will learn the reason why it has been set to null in the beginning.
class Node {
constructor(value){
this.value = value,
this.next = null
}
}
Listing 1- Node class in JavaScript
But why do we need pointers, though? Since a Node is an object, a list of nodes would be scattered across the memory, so the elements are not stored at contiguous memory locations. We need to connect them with some mechanism; that mechanism is pointers. Pointing to the memory location of the next node where the object is being stored.
We need a pointer to arrange elements in a linear fashion. Image 2 shows the visual representation of a LinkedList with 2 nodes.
Image 2- Pointers
Tail
In the above image, you can see there are 2 nodes, Node 1 has data which is 10, and then a pointer pointing to node 2. But Node 2 isn't pointing towards anything; in fact, it's pointing towards null; the same question we had before, what is the deal with this null?
Now we know pointers are used to point to the next node, but there has to be an end of the list. So when a list has the last element pointing towards nothing, it points towards null, specifying this is the last node, also known as a tail node. So in Image 2, Node 2 is a tail node.
Head
In the same way, we need to start somewhere, right? When we create the first element in a LinkedList, it's always ahead. i.e., we always start from the head. So the above image can also be seen as the below one.
Image 3- Head and Tail
2. Create a LinkedList class
As we said earlier, a LinkedList is a collection of nodes, so we need to create a class that adds, deletes, and searches these nodes. We always start with at least one node to create a LinkedList. So we can create this first node which would be the head of the list, with the help of the constructor.
class LinkedList{
//Creates a linkedlist with passed value.
constructor(value){
//Creates a head node
this.head = {
value: value,
next : null
};
//As there is only one element in the list, head is also a tail
this.tail = this.head;
//Length would be 1
this.length = 1;
}
}
Listing 2- LinkedList class with a constructor
In listing 2, you can see we are creating a single node in a constructor with a parameter's value, and since currently there is only one element in this LinkedList, this node is both head and tail, and the current length of this list would be 1.
Let's create an instance of LinkedList.
console.log('Creating a LinkList at constant time O(1): 20:');
const myLinkedList = new LinkedList(20);
console.log(myLinkedList);
Listing 3- Creates a LinkedList with a value of 20.
Run the code and check the console of the browser. You will be able to see the output as shown in image 4.
Image 4- Output of listing 1 and 2
3. Print a LinkedList
For that, we need to write a printList() method. The more elements you add to the list, the more complex the output will look. So to simplify, let's print just the values.
printList(){
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.head;
//Start iterating from the first node till you reach the last node
while(currentNode !== null){
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
Listing 5- Print the LinkedList
In the above listing, you can go through the comments; they are pretty self-explanatory. Now run the code again. This time, you'd be able to see the output as below.
Image 5- Printing LinkedList
Image 6- LinkedList with node 20
4. Add a new tail node
We learned how to add a head node; now, let's see how to append a node; every appended node becomes the new tail of the list.
//Add the node at the tail of the linkedlist
append(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
// Check if head is present or not, if head is empty creates a head
if (this.head == null){
this.head = node;
}
else{ //Else creates a tail
//We need to point current tail's next to the newNode
this.tail.next = newNode;
//Now make newNode a tail node
this.tail = newNode;
//Increase the length by 1
this.length++;
}
return this;
}
Listing 6- append method of LinkedList class
By calling the append method twice, let's append 2 nodes with 40 and 50.
console.log('Appendding Node at constant time O(1): 40 -> 50:');
myLinkedList.append(40).append(50);
console.log(myLinkedList.printList());
Listing 7- Adding elements in an array
Image 7- Output of Listing 6 and 7
Image 8- Appended 40 and 50
5. Adding a new head node
To add the new node as head, we must move the current head to the one position ahead.
//Add the node as a head of the linkedlist
prepend(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Points this node's next to the head
newNode.next = this.head;
//Now make this node a head node
this.head = newNode;
//Increase the length by 1
this.length++;
return this;
}
Listing 8- Adding a head
Now, call this method and prepend a node with the value 10.
console.log('Prepending Node at constant time O(1): 10:');
myLinkedList.prepend(10);
console.log(myLinkedList.printList());
Listing 9- Calling a prepend method
After adding a new node 10, your output would look like this,
Image 9- Output of listing 7 and 8
Image 10- Prepended 10
6. Inserting a node by index
Let's insert a new node at the given index. To insert an element in the middle, we have to traverse to the previous node, then divide the list into 2 parts; first, merge the right side of the list with the new node and then assign the left. Go through the comments to understand each step.
//Insertes a node at specified index, say we want to insert 30 at index 2
//Current list: 10 -> 20 -> 40 -> 50
insert(index, value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Counter to loop
let count = 1;
//Create a temp node to traverse through list, which will start from the head node
//Pointing to 10
let previousNode = this.head;
//Traverse the list one node before the specified index, which is previous node
while(count < index){
//Point previous node to next for iterating
previousNode = previousNode.next;
//Increase the count to compare it with index;
count++;
}
//When the loop ends you will be able to have a previous node. Which is 20 in this example.
//First, points new node's next to the previous node's next, so it can hold the list ahead of its index
//New node = 30, So new node will be 30 -> 40 -> 50
newNode.next = previousNode.next;
//Now just point previous node's next to new node.
//Merge left side of the list, 10 -> 20 -> 30 -> 40 -> 50
previousNode.next = newNode;
return this;
}
Listing 10- Inserting a node in a LinkedList
Let's call this method.
console.log('Inserting Node at index 2 with time complexty of O(n): 30');
myLinkedList.insert(2,30);
console.log(myLinkedList.printList());
console.log('Inserting at index 1: 15');
myLinkedList.insert(1,15);
console.log(myLinkedList.printList());
console.log('');
Listing 11- Inserting 30 and 15 in the LinkedList
Image 11- Output of listing 9 and 10
Image 12- Inserted 15 and 30
Delete operations
There are 4 possibilities for deleting a node from the linked list.
- Delete head
- Delete tail
- Delete at index
- Delete the node with the value
7. Delete head
Deleting the head is easy; make the next element a new one. Then reduce the length by 1.
deleteHead(){
this.head = this.head.next;
this.length--;
return this;
}
Listing 11- Delete head
console.log('Deleting Head-Node at constant time O(1): 10:');
myLinkedList.deleteHead();
console.log(myLinkedList.printList());
console.log('');
Listing 12- Calling a deleteHead method
Image 13- Output of listing 11 and 12
Image 14:-eted head node 10
8. Delete Tail
Traverse till the second last node in the list and point its next to null.
deleteTail(){
let secondLastNode = this.head;
while(secondLastNode.next.next !== null){
secondLastNode = secondLastNode.next;
}
secondLastNode.next = null;
this.length--;
return this;
}
Listing 13- Delete tail
console.log('Deleting Tail-Node at O(n) time: 70:');
myLinkedList.deleteTail();
console.log(myLinkedList.printList());
console.log('');
Listing 14- Calling a deleteTail
Image 15- Output of listing 13 and 14
Image 16- Deleted tail node 50
9. Delete a node by index
Now you know how to traverse to the previous node; once you reach the previous node, point it next to the next, next, which will skip the middle node.
Note: First, you must check whether the deleting node is the head.
deleteAtIndex(index){
//Check if index is head
if(index === 0){
//Appoint head to the next element
this.head = this.head.next;
this.length--;
return this;
}
let count = 1;
let previousNode = this.head;
while(count < index){
previousNode = previousNode.next;
count++;
}
previousNode.next = previousNode.next.next;
this.length--;
return this;
}
Listing 15- Delete node at the specified index
console.log('Deleting Node at index 2 with time complexty of O(n): 30:');
myLinkedList.deleteAtIndex(2);
console.log(myLinkedList.printList());
console.log('');
Listing 16- Calling deleteAtIndex method
Image 17- Output of Listing 15 and 16
Image 18- Deleted Node at index 2
10. Delete a node by value
Deleting a node by value. We will need 2 pointers for this, first to traverse the list and second to point to the previous node to update the previous node's next pointer. Following listing 17 is a step-by-step process of how we are supposed to achieve this. Follow the comments for a clear understanding.
deleteNodeByValue(value){
//Current node to loop through the list
let currentNode = this.head;
//Previous node to update its pointer to next.next node
let previousNode = null;
while(currentNode != null){
//Check if we find the value we are looking for
if(currentNode.value === value){
//Check if it is a head or not by comparing previous node with null
if (previousNode === null) {
//If it is head, then update head to nextnode
this.head = currentNode.next;
}
else{
//If it is not head then simply update previous node
previousNode.next = currentNode.next;
}
//Reduce length by 1
this.length--;
}
//Previous node will point to this node with every iteration
previousNode = currentNode;
//Current node will point to next node for iteration
currentNode = currentNode.next;
}
return this;
}
Listing 17- Deleting a node with the specified value
console.log('Deleting Node with value 40 with time complexty of O(n):');
myLinkedList.deleteNode(40);
console.log(myLinkedList.printList());
console.log('');
Listing 18- Calling DeleteNodeByValue
Image 19- Output of listing 17 and 18
Image 20- Deleted Node with value 40
11. Search an element
It's the simplest: traverse the list, compare the value, and return true or false.
searchElement(value){
let currentNode = this.head;
while(currentNode !== null){
if(currentNode.value === value) return true;
currentNode = currentNode.next;
}
return false;
}
Listing 19:-Searching for an element
console.log('Searching for value 20 with time complexty of O(n):');
console.log(myLinkedList.printList());
console.log(myLinkedList.searchElement(20));
console.log('Searching for value 50 with time complexty of O(n):');
console.log(myLinkedList.searchElement(50));
Listing 20- Searching for 20 and 50
Image 21- Output of listing 19 and 20
Image 22- Found element 15, returned false for node 50
LinkedList.js
And finally, here is the whole code. Let's call it LinkedList.js
class Node {
constructor(value){
this.value = value,
this.next = null
}
}
class LinkedList{
//Creates a linkedlist with passed value.
constructor(value){
//Creates a head node
this.head = {
value: value,
next : null
};
//As there is only one element in the list, head is also a tail
this.tail = this.head;
//Length would be 1
this.length = 1;
}
//Add the node at the tail of the linkedlist
append(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
// Check if head is present or not, if head is empty creates a head
if (this.head == null){
this.head = node;
} //Else creates a tail
else{
//We need to point current tail's next to the newNode
this.tail.next = newNode;
//Now make newNode a tail node
this.tail = newNode;
//Increase the length by 1
this.length++;
}
return this;
}
//Add the node as a head of the linkedlist
prepend(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Points this node's next to the head
newNode.next = this.head;
//Now make this node a head node
this.head = newNode;
//Increase the length by 1
this.length++;
return this;
}
//Insertes a node at specified index, say we want to insert 30 at index 2
//Current list: 10 -> 20 -> 40 -> 50
insert(index, value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Counter to loop
let count = 1;
//Create a temp node to traverse through list, point it to the head
//Pointing to 10
let previousNode = this.head;
//Traverse the list one node before the specified index
while(count < index){
//Points temp node to its next node
previousNode = previousNode.next;
//Increase the count to compare it with index;
count++;
}
//When the loop ends you will able have temp node pointing to the previous node of the index.
//First, points new node's next to the current node's next, so it can hold the list ahead of its index
//Current node = 20, New node = 30, So new node will be 30 -> 40 -> 50
newNode.next = previousNode.next;
//Now just point current node's next to new node.
//Merge left side of the list, 10 -> 20 -> 30 -> 40 -> 50
previousNode.next = newNode;
}
deleteHead(){
this.head = this.head.next;
this.length--;
}
deleteTail(){
let secondLastNode = this.head;
while(secondLastNode.next.next !== null){
secondLastNode = secondLastNode.next;
}
secondLastNode.next = null;
this.length--;
}
deleteAtIndex(index){
if(index === 0){
this.head = this.head.next;
this.length--;
return this;
}
let count = 1;
let previousNode = this.head;
while(count < index){
previousNode = previousNode.next;
count++;
}
previousNode.next = previousNode.next.next;
this.length--;
return this;
}
deleteNodeByValue(value){
//Current node to loop through the list
let currentNode = this.head;
//Previous node to update its pointer to next.next node
let previousNode = null;
while(currentNode != null){
//Check if we find the value we are looking for
if(currentNode.value === value){
//Check if it is a head or not by comparing previous node with null
if (previousNode === null) {
//If it is head, then update head to nextnode
this.head = currentNode.next;
}
else{
//If it is not head then simply update previous node
previousNode.next = currentNode.next;
}
//Reduce length by 1
this.length--;
}
//Previous node will point to this node with every iteration
previousNode = currentNode;
//Current node will point to next node for iteration
currentNode = currentNode.next;
}
}
searchElement(value){
let currentNode = this.head;
while(currentNode !== null){
if(currentNode.value === value) return true;
currentNode = currentNode.next;
}
return false;
}
printList(){
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.head;
//Start iterating from the first node till you reach the last node
while(currentNode !== null){
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
}
console.log('Creating a LinkList at constant time O(1): 20:');
const myLinkedList = new LinkedList(20);
console.log(myLinkedList.printList());
console.log('');
console.log('Appendding Node at constant time O(1): 40 -> 50:');
myLinkedList.append(40).append(50);
console.log(myLinkedList.printList());
console.log('');
console.log('Prepending Node at constant time O(1): 10:');
myLinkedList.prepend(10);
console.log(myLinkedList.printList());
console.log('');
console.log('Inserting Node at index 2 with time complexty of O(n): 30');
myLinkedList.insert(2,30);
console.log(myLinkedList.printList());
console.log('Inserting at index 1: 15');
myLinkedList.insert(1,15);
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Head-Node at constant time O(1): 10:');
myLinkedList.deleteHead();
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Tail-Node at O(n) time: 50:');
myLinkedList.deleteTail();
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Node at index 2 with time complexty of O(n): 30:');
myLinkedList.deleteAtIndex(2);
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Node with value 40 with time complexty of O(n):');
myLinkedList.deleteNodeByValue(40);
console.log(myLinkedList.printList());
console.log('');
console.log('Searching for value 20 with time complexty of O(n):');
console.log(myLinkedList.printList());
console.log(myLinkedList.searchElement(20));
console.log('Searching for value 50 with time complexty of O(n):');
console.log(myLinkedList.searchElement(50));
Listing 21- LinkedList.js
Image 23- Final output of LinkedList.js
Summary
Today we learned what LinkedList is. What are the different operations that can be performed on LinkedList? How expensive could each operation be? Later we saw how to code those operations in javascript.
This is a single LinkedList; there are other types of LinkedList, such as doubly LinkedList and circular LinkedList. We will learn about them in upcoming articles.
I hope you found this article helpful and helped you understand the basics of the linked list.
Happy coding, Cheers.
If you want to update the code better, feel free to fork in the following branch.
LinkedList.js
Join the conversation! Your thoughts help the community grow.