LinkedList in JavaScript

Introduction to LinkedList in JavaScript

JavaScript LinkedList using a doubly linked list implementation to store the elements. It is providing linked list data-structure. There is no pre-defined linked list in JavaScript, so we must implement the linked list class with dynamic features. Dynamic means it can grow or shrink as we needed. As like array, linked list also stores the elements sequentially but not continuously.

Important Points about JavaScript LinkedList are:

• JavaScript LinkedList instance can contain duplicate elements.
• It can maintain inserting order of elements.
• Its manipulation is fast because no shifting of elements needed.

What can we do with LinkedList in JavaScript?

• Stacks and Queues implementation.
• Graphs implementation.
• Linked list blocks are used for dynamic memory allocation.
• Arithmetic operations on long integers.

Syntax:

class Node { //JavaScript user class
constructor(value)   // constructor in JavaScript
{
//initialization of elements
this.value = value;
this.next = null
// Supporting functions
// check whether the list is empty or not function isEmpty()
// displaying the list function displayList()
//JavaScript functions
// add() function
// insertion function at index insertionAt()
// removing element function remove()
//find size of the list function sizeOf()
}
}

Examples of LinkedList in JavaScript

As it is user implementation class, we see function by function for better understanding. Here each function implementation as one example. At last we will put together all the code and see the output.

1. Creating Linked List

Code:

//creating user defined Linked List function
function LinkedList() {
this.pointer = null;
}

Explanation: Creating user defined Linked List for adding the elements.

2. Implementing isEmpty() Function

Code:

//implementing isEmpty() function
LinkedList.prototype.isEmptyLinkedList = function() {
return this.pointer === null;
};
//isEmpty() function logic
if (this.isEmptyLinkedList()) {
this.pointer = currententNode;
return;
}

Explanation: Creating user defined isEmptyLinkedList() function for checking whether the given list is empty or not.

3. Implementing sizeOf() Function

Code:

//implementing sizeOf() function
LinkedList.prototype.sizeOfLinkedList = function() {
var presentValue = this.pointer;
var tempCount = 0;
while (presentValue !== null) {
tempCount++;
presentValue = presentValue.next;
}
return tempCount;
};

Explanation: Creating user defined sizeOfLinkedList() function for checking the size of the linked list.

4. Implementing addBefore() and addAfter() Functions

Code:

//implementing addBefore() function
LinkedList.prototype.addBefore = function(value) {
var currententNode = {
content: value,
next: this.pointer
};
this.pointer = currententNode;
};
//implementing addAfter() function
LinkedList.prototype.addAfter = function(value) {
var currententNode = {
content: value,
next: null
};

Explanation: Creating user defined addBefore() function and addAfter() function , because linked list is doubly linked list so we have to implement a class such away that it can allow the elements wherever it wants like before the element or after the element.

5. Implementing contains() Function

Code:

//implementing contains() function
LinkedList.prototype.isContainsElement = function(value) {
var presentValue = this.pointer;
while (presentValue !== null) {
if (presentValue.content === value) {
return true;
}
presentValue = presentValue.next;
}
return false;
};

Explanation: Creating user defined isContainsElement() function for checking whether the linked list have that element or not.

6. Implementing remove() Function

Code:

//implementing remove() function
LinkedList.prototype.removeElement = function(value) {
if (!this.isContainsElement(value)) {
return;
}
if (this.pointer.content === value) {
this.pointer = this.pointer.next;
return;
}
var previous = null;
var current = this.pointer;
while (current.content !== value) {
previous = current;
current = current.next;
}
previous.next = current.next;
};

Explanation: Creating user defined removeElement() function for removing the single element at a time from the linked list.

7. Implementing display() Function

Code:

//implementing display() function
LinkedList.prototype.displayLinkedList = function() {
var result = '[';
var presentValue = this.pointer;
while (presentValue !== null) {
result += presentValue.content;
if (presentValue.next !== null) {
result += ', ';
}
presentValue = presentValue.next;
}
result += ']';
document.write(result+"<br>");
};

Explanation: Creating user defined displayLinkedList() function for displaying total current linked list to the end user.

Total Example by adding above all sub parts into single code to see our implemented code:

All function of Linked List Example:

Code:

<script>
function LinkedList() {
this.pointer = null;
}
LinkedList.prototype.isEmptyLinkedList = function() {
return this.pointer === null;
};
LinkedList.prototype.sizeOfLinkedList = function() {
var presentValue = this.pointer;
var tempCount = 0;
while (presentValue !== null) {
tempCount++;
presentValue = presentValue.next;
}
return tempCount;
};
LinkedList.prototype.addBefore = function(value) {
var currententNode = {
content: value,
next: this.pointer
};
this.pointer = currententNode;
};
LinkedList.prototype.addAfter = function(value) {
var currententNode = {
content: value,
next: null
};
if (this.isEmptyLinkedList()) {
this.pointer = currententNode;
return;
}
var presentValue = this.pointer;
while (presentValue.next !== null) {
presentValue = presentValue.next;
}
presentValue.next = currententNode;
};
LinkedList.prototype.isContainsElement = function(value) {
var presentValue = this.pointer;
while (presentValue !== null) {
if (presentValue.content === value) {
return true;
}
presentValue = presentValue.next;
}
return false;
};
LinkedList.prototype.removeElement = function(value) {
if (!this.isContainsElement(value)) {
return;
}
if (this.pointer.content === value) {
this.pointer = this.pointer.next;
return;
}
var previous = null;
var current = this.pointer;
while (current.content !== value) {
previous = current;
current = current.next;
}
previous.next = current.next;
};
LinkedList.prototype.displayLinkedList = function() {
var result = '[';
var presentValue = this.pointer;
while (presentValue !== null) {
result += presentValue.content;
if (presentValue.next !== null) {
result += ', ';
}
presentValue = presentValue.next;
}
result += ']';
document.write(result+"<br>");
};
//Checking user created Linked List functionality
var linkedList = new LinkedList();
//adding the elements
linkedList.addAfter(100);
linkedList.addAfter(200);
linkedList.addAfter(300);
linkedList.addAfter(300);
linkedList.addBefore(400);
linkedList.addAfter(100);
linkedList.addAfter(200);
linkedList.addAfter(300);
linkedList.addAfter(300);
linkedList.addBefore(400);
//displaying linked list
linkedList.displayLinkedList(); //[400, 400, 100, 200, 300, 300, 100, 200, 300, 300]
//removing elements
document.write("Removing 200 from linkedList =>"+"<br>");
linkedList.removeElement(200);
//displaying linked list
linkedList.displayLinkedList(); //[400, 400, 100, 300, 300, 100, 200, 300, 300]
//size of linked list
document.write("Size of linkedList:");
document.write(linkedList.sizeOfLinkedList()+"<br>"); //9
//contains the given element
document.write("Is 400 existing in linkedList?:");
document.write(linkedList.isContainsElement(400)+"<br>");//true
//contains the given element
document.write("Is 500 existing in linkedList?:");
document.write(linkedList.isContainsElement(500)+"<br>"); //false
</script>

Output:

Conclusion

We can also implement user defined function for adding, removing, finding the size, is linked list empty, is linked list contains specific element only, displaying out put in JavaScript. This linked list works same as Java Linked list.