Complete guide to Linked Lists in JavaScript
A Linked List is a sequential structure that consists of a sequence of items in linear order which are linked to each other.
class Node {
constructor(element)
{
this.element = element;
this.next = null
}
}
Here, a node is been created, using a constructor, which stores two parameters:
- element : value
- next : location to the next node
The location to the next node is stored as a null value in the beginning.
Now let us implement in the LinkedList class
// LinkedList class
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
// Main Functions
// add(element)
// insertAt(element, location)
// removeFrom(location)
// removeElement(element)
// Helper Functions
// indexOf(element)
// isEmpty()
// sizeOfList()
// printList()
}
The above program displays the constructor and the list of methods to be implemented. The class comprises of two property:
- head : stores the first node of the list
- size : stores the size of the list
Main Functions
add(element)
// adds an element at the end of list
add(element) {
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
Our approach here is first if the list is empty, we are adding the element in the begining, else we are continuously pushing the element in the next node and adding the element in the end. current is used to iterate through the list after every iteration we update it to be the next of the current node. If next is null(the last element of a list contains null in the next) then we add the element to the list.
insertAt(element, index)
// insert element at the position 'index' of the list
insertAt(element, index) {
if (index > 0 && index > this.size)
return false;
else {
// creates a new node
var node = new Node(element);
var current, previous;
current = this.head;
// add the element to the first index
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
current = this.head;
var it = 0;
// iterate over the list to find the position to insert
while (it < index) {
it++;
previous = current;
current = current.next;
}
// adding an element
node.next = current;
previous.next = node;
}
this.size++;
}
}
Our approach here is if the index is zero we add an element at the front of the list and make it head, if the index is the last position of the list we append the element at the end of the list else, if the index is between 0 or size – 1 we iterate over to the index and add an element at that index
previous holds the previous of current node
removeFrom(index)
// removes an element from the 'index'th location
removeFrom(index) {
if (index > 0 && index > this.size)
return -1;
else {
var current, previous, it = 0;
current = this.head;
previous = current;
// deleting first element
if (index == 0) {
this.head = current.next;
} else {
// iterate over the list to the position to remove an element
while (it < index) {
it++;
previous = current;
current = current.next;
}
// remove the element
previous.next = current.next;
}
this.size--;
// return the remove element
return current.element;
}
}
Our approach here is if the index is 0 then we remove the head and make the next node head of the list, if the index is size – 1 then we remove the last element from the list and make previous the last element, lastly if it is in between 0 to size – 1 we remove the element by using previous and current node.
removeElement(element)
// removes a given element from the list
removeElement(element) {
var current = this.head;
var previous = null;
// iterate over the list
while (current != null) {
// comparing element with current element
// if found
// then remove the element
// and return true
if (current.element == = element) {
if (previous == null) {
this.head = current.next;
} else {
previous.next = current.next;
}
this.size--;
return current.element;
}
previous = current;
current = current.next;
}
return -1;
}
This function is nearly the same as removeFrom(index), just here, we are searching the element and removing it.
Helper functions
indexOf(element)
// finds the index of element
indexOf(element) {
var count = 0;
var current = this.head;
// iterae over the list
while (current != null) {
// compare each element of the list with given element
if (current.element == element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
In this method, we iterate over the list to find the index of an element. If it is not present in the list it returns -1 instead.
isEmpty()
// checks the list for empty
isEmpty() {
return this.size == 0;
}
In this method we check for the size property of the LinkedList class, and if its zero then the list is empty.
sizeOfList()
// gives the size of the list
sizeOfList() {
console.log(this.size);
}
Simply displays the size property of the LinkedList class.
printList()
// prints the list items
printList() {
var current = this.head;
var str = "";
while (current) {
str += current.element + " ";
curr = current.next;
}
console.log(str);
}
In this method, we iterate over the entire list and concatenate the elements of each node and print it.
Implementation
Now we will use different functions from the above.
// creating an object for the Linkedlist class
var list = new LinkedList();
// testing isEmpty on an empty list
console.log(list.isEmpty());
// returns true
// adding element to the list
list.add(10);
list.printList();
// prints 10
console.log(list.sizeOfList());
// returns 1
// adding more elements to the list
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.printList();
// returns 10 20 30 40 50
// prints 50 from the list
list.removeElement(50);
list.printList();
// prints 10 20 30 40
console.log("Index of 40 " + list.indexOf(40));
// returns 3
list.insertAt(60, 2);
// insert 60 at second position
list.printList();
// list contains 10 20 60 30 40
console.log("Is List Empty ? " + list.isEmpty());
// returns false
console.log(list.removeFrom(3));
// remove 3rd element from the list
list.printList();
// prints 10 20 60 40
Acknowledgement
If I have made any mistake in the article please comment on it.