Post

## 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

1. How to create a node
6. Inserting a node in between a LinkedList
7. How to delete a head node
8. Delete a tail node
9. Delete a node by index
10. Delete a node by value
11. 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.

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.

## 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){
value: value,
next : null
};
//As there is only one element in the list, head is also a tail
//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:');

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

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

//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(' -> ');
}``````

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 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);

}
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:');

Listing 7- Adding elements in an array

Image 7- Output of Listing 6 and 7

Image 8- Appended 40 and 50

``````//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

//Now make this node a head node

//Increase the length by 1
this.length++;

return this;
}``````

Now, call this method and prepend a node with the value 10.

``````console.log('Prepending Node at constant time O(1): 10:');

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

//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');
console.log('Inserting at index 1: 15');
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.

2. Delete tail
3. Delete at index
4. Delete the node with the value

Deleting the head is easy; make the next element a new one. Then reduce the length by 1.

``````deleteHead(){
this.length--;
return this;
}``````

``````console.log('Deleting Head-Node at constant time O(1): 10:');
console.log('');``````

Listing 12- Calling a deleteHead method

Image 13- Output of listing 11 and 12

## 8. Delete Tail

Traverse till the second last node in the list and point its next to null.

``````deleteTail(){
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:');
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){
if(index === 0){
//Appoint head to the next element
this.length--;
return this;
}
let count = 1;
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:');
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

//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) {
}
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):');
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){
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('Searching for value 50 with time complexty of O(n):');
``````

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

And finally, here is the whole code. Let's call it LinkedList.js

``````class Node {
constructor(value){
this.value = value,
this.next = null
}
}

//Creates a linkedlist with passed value.
constructor(value){
value: value,
next : null
};
//As there is only one element in the list, head is also a tail
//Length would be 1
this.length = 1;
}

append(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
} //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;
}

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
//Now make this node a head node
//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

//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;
}

this.length--;
}

deleteTail(){
while(secondLastNode.next.next !== null){
secondLastNode = secondLastNode.next;
}
secondLastNode.next = null;
this.length--;
}

deleteAtIndex(index){
if(index === 0){
this.length--;
return this;
}
let count = 1;
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

//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) {
}
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){
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
//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:');
console.log('');

console.log('Appendding Node at constant time O(1): 40 -> 50:');
console.log('');

console.log('Prepending Node at constant time O(1): 10:');
console.log('');

console.log('Inserting Node at index 2 with time complexty of O(n): 30');
console.log('Inserting at index 1: 15');
console.log('');

console.log('Deleting Head-Node at constant time O(1): 10:');
console.log('');

console.log('Deleting Tail-Node at O(n) time: 50:');
console.log('');

console.log('Deleting Node at index 2 with time complexty of O(n): 30:');
console.log('');

console.log('Deleting Node with value 40 with time complexty of O(n):');
console.log('');

console.log('Searching for value 20 with time complexty of O(n):');
console.log('Searching for value 50 with time complexty of O(n):');
``````

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.