Last Updated on December 13, 2022 by Prepbytes
In this article we will study javascript linked list implementation. A linked list is a dynamic data structure as we can add or remove nodes easily. A linked list stores data in the form of non-contiguous memory blocks in memory. It is similar to an array as it is linear but offers dynamic size.
A node of a linked list needs to store at least $2$ information:
- The data stored in the node
- The pointer to the next node
While creating a new node, we can initialize its value with the value passed and next as null.
Let us look at the implementation of a javascript linked list implementation.
class Node {
constructor(val){
this.val = val;
this.next = null;
}
}
Now let’s further implement the javascript linked list implementation:
push_front(x)
push_front(x) will add a new node containing the value as x, to the front of the linked list and the head will be updated to point to this new node.
push_front(x){
let node = new Node(x);
node.next = this.head;
this.head = node;
this.size ++;
}
push_back(x)
push_back(x) will add a new node with value x at the end of the linked list
- If the linked list is empty, then push_back will be the same as push_front and the new node will be the head node.
- Else we traverse till the last node and add a new node there
push_back(x){
if(this.head==null){
push_front(x);
return;
}
// reach the node just before the end
let curr = this.head;
while(curr.next!==null){
curr = curr.next;
}
// now curr node is the last node
// add a new node here
let node = new Node(x);
curr.next = node;
this.size ++;
}
pop_front()
pop_front() will remove and return the value in the node at the front of the linked list. If the linked list is empty, then this function will return null.
pop_front(){
// if linked list is empty
if(this.head === null) return null;
// store the front node in temp
let temp = this.head;
// modify the head to point to the next node
this.head = this.head.next;
// decrease size of linked list
this.size --;
// return the value in temp
return temp.val;
}
pop_back()
pop_back() will remove and return the value in the node at the end of the linked list. If the linked list is empty, this function will return null.
pop_back(){
if(this.head === null) return null;
// reach the node just before the end
let curr = this.head;
while(curr.next!==null){
curr = curr.next;
}
let back = curr.val;
// to disconnect the last node
// set the next pointer of node just before
// the last node as null
curr.next = null;
this.size --;
return back;
}
Implementation of LinkedList class along with all above functionalities
class linkedList {
constructor(){
this.head = null;
this.size = 0;
}
// to add an element x at the front of the linked list
push_front(x){
let node = new Node(x);
node.next = this.head;
this.head = node;
this.size ++;
}
// to add an element at the back of the linked list
push_back(x){
if(this.head==null){
push_front(x);
return;
}
let node = new Node(x);
let curr = this.head;
while(curr.next!==null){
curr = curr.next;
}
curr.next = node;
this.size ++;
}
// to remove and return an element which is at the front of
// the linked list
pop_front(){
if(this.head === null) return null;
let temp = this.head;
this.head = this.head.next;
this.size --;
return temp.val;
}
// to remove and return an element from the back of
// the linked list
pop_back(){
if(this.head===null) return null;
let curr = this.head;
while(curr.next!==null){
curr = curr.next;
}
let back = curr.val;
curr.next = null;
this.size --;
return back;
}
// to find out whether the linked list is empty or not
isEmpty(){
return this.size === 0;
}
// to find out the size of the linked list
getSize(){
return this.size;
}
// to print the linked list
printIt(){
let temp = this.head;
let s = "";
while(temp !== null){
s += temp.val + " ";
temp = temp.next;
}
console.log(s);
}
// to find out the position of an element x in
// the linked list
positionOf(x){
let temp = this.head;
let pos = 1;
while(temp !== null){
if(temp.val === x){
return pos;
}
temp = temp.next;
pos ++;
}
// if x isn't found
return -1;
}
}
In this article, we understood how to implement a LinkedList in javascript. To understand better how javascript linked list implementation, I would highly recommend you solve some problems on Linked List, which our expert mentors curate at PrepBytes, you can follow this link Linked List.
FAQs related to javascript linked list implementation
1. Can we implement a linked list in javascript?
The linked list in Javascript is a data structure that stores a collection of ordered data that can only be accessed sequentially. The data element (technically a node) consists of some information and a pointer.
2. How do you create a linked list in javascript?
Javascript linked list implementation:
- Create a function for creating a new Node object.
- Create the LinkedList class with the proper constructor.
- Create the insert() and print() methods.
- Create the remove() method to remove nodes.
- Create the methods to remove and insert from the head.