Implementation of Linked List For Memory Management In JavaScript

Implementation of Linked List in JavaScript For Better Memory Management

In this blog, we will be implementing a LinkedList data structure in Javascript. A linked list is a linear data structure, in which we can add or remove elements at ease for example- array, but linked list store the elements sequentially not contiguously. LinkedList connected with the links and links contains the data and another link. 

Why use a linked list?

The primary benefit of the linked list is that they can contain an arbitrary number of values while using only the amount of memory necessary for those values. In previous computers where memory was scarce at that time array in c required you to specify how many items the array could maintain and the program will contain that amount of memory which means no another program will use that memory, so for this problem, we use Linked List data structure for better memory management. In Javascript, you might not use this all over your career but the linked list is still a good way to learn about creating data structure.

Ex: // User defined class node class Node {      constructor(element)    { this.elemenet = elemenet; this.next = null    } }

In this code, we define a class Node which has two properties:-
1. Element:- Element holds the data of a node.
2. Next:- Next holds the pointer to the next node, which is initialized to the null value.

Ex- Implementation of Linked List class: class LinkedList {    constructor()    {        this.head = null;        this.size = 0;    } }

In this class we add some functions like- add(element), insertAt(element, location), removeFrom(location), removeElement(element). and some helper methods like - isEmpty, size_Of_List, and PrintList.

Linked List class has two properties:
1. head:- head stores the first node of a List
2. size:- size indicates the number of nodes in a list.

* add(element) - Add an element in a list.

If the list is empty, add an element, which will be the head.
If the list is not empty, iterate to the list's end and add an element there.

Ex:- 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++; }

* insertAt(element, index) – It inserts an element at the given index in a list.

In order to add an element at the end of the list we consider three conditions as follows:
If the index is 0, we add an element at the front of the list and call it head.
If the index is the last position of the list, we append the element at the end. If the index is between 0 and size -1, we iterate over to the index and add an element there.
In the above method, prev holds the previous current node.

Ex:- insertAt(element, index) {    if (index > 0 && index > this.size)        return false;    else {        // creates a new node        var node = new Node(element);        var curr, prev;          curr = this.head;          // add the element to the first index        if (index == 0) {            node.next = head;            this.head = node;        } else {            curr = this.head;            var it = 0;              // iterate over the list to find the position to insert            while (it < index) {                it++;                prev = curr;                curr = curr.next;            }              // adding an element            node.next = curr;            prev.next = node;        }        this.size++;    } }

* removeFrom(index) – It removes and returns an element from the list from the specified index
 
We evaluate three circumstances for removing an element from the list:
If the index is 0, we remove the head and make the next node the head of the list. If the index is size -1, we remove the last element and make prev the last element. If the index is between 0 and size -1, we remove the element using prev and the current node.

Ex:- removeFrom(index) {    if (index > 0 && index > this.size)        return -1;    else {        var curr, prev, it = 0;        curr = this.head;        prev = curr;          // deleting first element        if (index == = 0) {            this.head = curr.next;        } else {            // iterate over the list to the position to removce an element            while (it < index) {                it++;                prev = curr;                curr = curr.next;            }              // remove the element            prev.next = curr.next;        }        this.size--;          // return the remove element        return curr.element;    } }

*removeElement(element) – This method removes element from the list. It returns the removed element, or if it's not found it returns -1.

Ex:- removeElement(element) {    var current = this.head;    var prev = null;      // iterate over the list    while (current != null) {        // comparing element with current element if found then remove the and return true        if (current.element == = element) {            if (prev == null) {                this.head = current.next;            } else {                prev.next = current.next;            }            this.size--;            return current.element;        }        prev = current;        current = current.next;    }    return -1; }

 
Helper Methods

Let us declare some helper methods for working with LinkedList. In this method, we loop through the list to determine the index of an entry. If it is not in the list, it returns -1.

1. isEmpty() – it returns true if the list is empty. In this method, we check for the size property of the LinkedList class, and if it's zero then the list is empty.

2. size_of_list() – It returns the size of list

3. printList() – It prints the contents of the list. In this method, we iterate over the entire list and concatenate the elements of each node and print it.

Ex:-Now, let's use the LinkedList class and the different methods described above. // creating an object for the Linkedlist class var list = new LinkedList();   // testing isEmpty on an empty list returns true console.log(list.isEmpty());   // adding element to the list list.add(10);   // prints 10 list.printList();   // returns 1 console.log(list.size_of_list());   // adding more elements to the list list.add(20); list.add(30); list.add(40); list.add(50);   // returns 10 20 30 40 50 list.printList();   // prints 50 from the list console.log("is element removed ?" + list.removeElement(50));   // prints 10 20 30 40 list.printList();   // insert 60 at second position ll contains 10 20 60 30 40 list.insertAt(60, 2);   list.printList();   // returns false console.log("is List Empty ? " + list.isEmpty());   // remove 3rd element from the list console.log(list.removeFrom(3));   // prints 10 20 60 40 list.printList();