Linked List is an ordered collection of data elements. In linked list the data will be represented in Nodes. Node has two parts, the first part will be holding the data of the element and second part of the node (pointer) will store the address of the very next node. In linked list elements are stored in a sequential manner.
Node: This represents each element in the linked list. It consists of 2 parts, data and next.
Head: The reference to the first element is called a head.
Next: This is the pointer that points to the next node in the linked list.
Types of Linked List
There are three types of linked list:
- Singly Linked List: In this type of linked list, each node in the list is connected only to the next node in the list.
- Doubly Linked List: In this type of linked list, each node in the list is connected to the next and the previous node.
- Circular Linked List: In this type of linked list, the last node is connected to the first node.
Implementations of Linked List
Defining node class and liked list class, this is basically the prerequisite in order to implement a linked list in JavaScript. In this step, 2 classes namely one for the nodes and the other for the linked list need to be created.
The Node class represents a single node in the linked list. It has two properties which are data and next. The data property is used to store the actual data of the node, whereas the next property is a reference to the next node in the list. The Node class consists of a constructor that initializes the data and next property when creating a new Node.
classNode{constructor(data){this.data = data;this.next =null;}}
The LinkedList class is a representation of the linked list itself. It has a head property that refers to the first node in the list. The LinkedList class also has a constructor that initializes the head property when creating a new LinkedList.
classLinkedList{constructor(){this.head =null;this.tail =null;this.length =0;}}
The LinkedList class also consists of a method that allows you to insert, delete, and search for nodes in the list while simultaneously allowing other operations like printing the list, counting the elements, reversing the list and so on.
Inserting a Node
To insert a node in the linked list, we need to create a new node first and need to assign the data to it. Then we need to check if the head is null, if it is null then we need to assign the new node to the head. If the head is not null, then we need to traverse the list till the last node and assign the new node to the next of the last node.
insert(data){let node =newNode(data);if(!this.head){this.head = node;this.tail =this.head;}else{this.tail.next = node;this.tail = node;}this.length++;returnthis;}
Searching a Node
If there is a need to search a element in the linked list we can simply traverse the linked list and check if current node data is equal to the data we are searching for. If we find the data we are searching for, we can return the node.
search(data){let current =this.head;while(current){if(current.data === data){return current;}
current = current.next;}returnnull;}</pre>
Deleting a Node
If we want to delete a node from the linked list, let's say you have node prev and node current and you want to delete the node current . You can simply assign the next of the prev to the next of the current and the node current will be deleted.
delete(data){if(!this.head)returnnull;if(this.head.data === data){this.head =this.head.next;this.length--;returnthis;}let current =this.head;let prev =null;while(current){if(current.data === data){
prev.next = current.next;this.length--;returnthis;}
prev = current;
current = current.next;}returnnull;}</pre>
Printing the Linked List
You can print the elements of a linked list by traversing through the list and printing the data of each node.
print(){let current =this.head;while(current){
console.log(current.data);
current = current.next;}}</pre>
Code Example
Following is an example of a linked list implementation in JavaScript.
<!DOCTYPE html><head><title>Linked List</title></head><body><p id ="demo"></p><script>classNode{constructor(data){this.data = data;this.next =null;}}classLinkedList{constructor(){this.head =null;this.tail =null;this.length =0;}insert(data){let node =newNode(data);if(!this.head){this.head = node;this.tail =this.head;}else{this.tail.next = node;this.tail = node;}this.length++;returnthis;}search(data){let current =this.head;while(current){if(current.data === data){return current;}
current = current.next;}returnnull;}delete(data){if(!this.head)returnnull;if(this.head.data === data){this.head =this.head.next;this.length--;returnthis;}let current =this.head;let previous =null;while(current){if(current.data === data){
previous.next = current.next;this.length--;returnthis;}
previous = current;
current = current.next;}returnnull;}print(){let current =this.head;let output ="";while(current){
output += current.data +" ";
current = current.next;}
document.getElementById("demo").innerHTML = output;}}let list =newLinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
list.print();</script></body></html>
Output
Following is the output of the above code.
1 2 3 4 5
In the above example, we have created a linked list with elements 1, 2, 3, 4, and 5. We have inserted these elements into the linked list and printed the list.
