Linked list in JavaScript

Most taught data structure in computer science is linked list. Among that, singly linked list is most commonly used. Most of the JavaScript newbies or the "Back-end web developers" implements almost everything using Arrays. Here in this post I will be showing another alternate yet quick way (using linked list) to solve few real life problems in JavaScript.

Linked list -

Image explains a lot, each node in a linked list holds two items, first item is the data while the other one is the pointer to the next item.

There are a few catches you might want to know -

• Suppose there are 10 nodes in a linked list (numbered 1 to 10). If the pointer of node 1 is changed to 3 instead of 2 (1 ---> 3 ---> 4 ---> 5 so on..) then JavaScript garbage collector will free the memory space of node 2 since node 2 has no references
• Linked list allows insertion or deletion of node at any place but does not allow random access
• Linked list is a sequential access data structure. It will cost you a lot to find the element at the 6th position or 5th position or nth position
• Use Linked list when you want to insert or delete an element where you have a huge amount of data, that's where Array will cost you a lot

Before moving forward, do you remember your training on object references, Luke? Well, you might want to recall how object references works in JavaScript -

var movie = {

    name: 'Star wars',

    rating: 8.5

}

var item = movie;

item.rating = 9;

console.log(movie.rating);

You guessed it right, it will print 9. There is only one memory space which is being referenced by both movie and the item variables. It really doesn't matter, through which variable you are changing that memory's value. This concept will benefit us while creating a linked list.

Implementation of Linked List -

A simple node -

var node1 = {

    data: null,

    next: null

}

We can assign some data to it -

node1.data = 'Empire strikes back';

Creating next node

var node2 = {

    data: null,

    next: null

}

node2.data = 'Return of the jedi';

node1.next = node2;

Pretty easy! Right? Of course, manually creating a node each time when needed is not the solution that we are looking for. A better way is to create a List object, which implements all the internal logic of the linked list and only exposes some utility methods for the user.

function List() {

    this.head = null;

    this.end = null;

}

Initially Linked list's head and end properties are set to null. That means the list is empty.

Now it should expose a method that can easily create a node

this.createNode = function() {

    return {

        data: null,

        next: null

    }

}

Next thing should be adding this newly created node in our existing list. While adding the new node in the list, you must consider a few things -

• By default, new node should always be added at the end of the list
• Before adding new element there should be a check of empty list. if empty, new element should be added at the beginning of the list

Adding node in the list -

this.addNode = function(data) {

    // Checking if list is empty

    if (this.start === null) {

        // Creating a new node

        this.head = List.createNode();

        // since we have only one node in list, start and end will point to same node

        this.end = this.start;

    } else {

        // Appending newly created node after the end of the list

        this.end.next = List.createNode();

        // Setting last node as end node

        this.end = this.end.next;

    }

    // Finally assigning data to the newly created node

    this.end.data = data;

}

so far your List function looks like -

function List() {

    this.head = null;

    this.end = null;

    this.createNode = function() {

        return {

            data: null,

            next: null

        }

    }

    this.addNode = function(data) {

        // Checking if list is empty

        if (this.start === null) {

            // Creating a new node

            this.head = List.createNode();

            // since we have only one node in list, start and end will point to same node

            this.end = this.start;

        } else {

            // Appending newly created node after the end of the list

            this.end.next = List.createNode();

            // Setting last node as end node

            this.end = this.end.next;

        }

        // Finally assigning data to the newly created node

        this.end.data = data;

    }

}

Now you can create the linked list with multiple nodes dynamically -

var list = new List();

for (var x = 0; x < 5; x++) {

    list.addNode(x);

}

Now that you have base structure ready, you can add multiple methods to your list.

Adding node at start of the list -

this.appendAtFirst = function(data) {

    var tempNode = List.createNode();

    tempNode.next = this.head;

    this.head = tempNode;

    tempNode.data = data;

}

Inserting after a node -

Inserting in between the linked list is way too easier as compared to array. Why you ask? Because array moves a lot of data in order to make space for new node while the linked list will simply changes pointer of one node. So, when you are dealing with huge amount of data that requires insertion and deletion, better to prefer linked list over array.

this.insertAfter = function(n, data) {

    // n: node after which data to be inserted

    var instance = this.head;

    // Start traversing from the first/head element until you reach nth node

    while (instance !== null) {

        if (instance.data === n) {

            var tempNode = List.createNode();

            tempNode.data = data;

            tempNode.next = instance.next;

            if (instance == this.end) {

                this.end = tempNode;

            }

            instance.next = tempNode;

            return;

        }

        instance = instance.next;

    }

}

Removing a node -

For removing any node, you just need to change the pointer of it's previous node to point to it's next node. After this, your node will not be having any reference. JavaScript garbage collector will delete that node for you. So no need to explicitly delete any element.

this.remove = function(data) {

    // data - Node having data needs to be deleted

    var instance = this.head;

    var previous = this.head;

    // Traverse list from head/start node

    while (instance !== null) {

        if (data === instance.data) {

            if (instance === this.start) {

                this.head = instance.next;

                return;

            }

            if (instance == this.end)

                this.end = previous;

            previous.next = instance.next;

            return;

        }

        previous = instance;

        instance = instance.next;

    }

}

List traversal -

Now it is easy to figure out how to traverse a list.

this.traverse = function() {

    var instance = this.head;

    while (instance !== null) {

        console.log(instance.data);

        instance = instance.next;

    }

}

Follow this blog for more JavaScript hacks!