JavaScript

How to implement a Linked List data structure in Javascript?

Javascript is a web programming language that is used to make our web pages and web applications dynamic and interactive by giving them the ability to think and act. Like any other programming language, JavaScript offers us arrays which are a collection of different elements stored in a single variable. The limitation of an array is that it is stored consecutively at a particular memory in our system hence to solve this problem we use a Linked List.

Linked List

The Linked Lists are like arrays except that in a linked list the items aren’t saved in a specific memory location or index and every element is a separate independent object that is connected to the next element by having a pointer or link to that element.

Every linked list contains a head(first node), length(size of the linked list), and a tail(last node) property, and each element in a linked list is called a node and every node has a value stored in it and the link to the next node. If the current node is the tail then the link will be null that is not pointing to any other node. The linked list doesn’t contain indexes unlike arrays that have indexes e.g 0,1,2.. and so on.

Linked Lists in JavaScript can be demonstrated as follows:

// Linked List
const LinkedList = {
    // every node has a value and pointer
    // first pointer is the header
    head: {
        value: 6
        next: {
            value: 10                                            
            next: {
                value: 12
                next: {
                    value: 3
                    next: null  
                    }
                }
            }
        }
    }
};

Linked List advantage is that elements(nodes) are easily added and removed from the linked list without adjusting the whole linked list. The disadvantage of a linked list is that it needs more memory for storage as now we have an extra pointer that we are storing along with the value of the element.

Linked Lists are of three types which are described below:

  • The singly linked list has only one pointer pointing to the node next to it.
  • The doubly linked is based on two-pointers in which the first one points to the node that is behind it and the second one points to the node next to it.
  • The circular linked list whose tail contains a pointer to the head and hence forms a cycle.

Linked List Implementation

Let us first create a node that has two properties a value and a pointer for which we will create a class with the name of ListNode that has these two properties:

class ListNode {
    constructor(value) {
        this.value = value
        this.next = null                
    }
}

Now that we know how to create a node let us create a linked list where the default value of the head will be null:

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

Let us now initialize the linked list with two nodes and add a pointer from the head or node 1 to the second node:

var node1 = new ListNode(3);
var node2 = new ListNode(4);
node1.next = node2;

The next step is to initialize the linked list with node1 in the following manner:

var list = new LinkedList(node1);

The whole code is given below with console logging the node2 value:

// creating node
class ListNode {
    constructor(value) {
        // Constructor initializing value and the next pointer
        this.value = value
        this.next = null                
    }
}

class LinkedList {
    // Linked List Constructor
    constructor(head = null) {
        this.head = head
    }
}

// initializing created nodes
var node1 = new ListNode(3);
var node2 = new ListNode(4);
node1.next = node2;

// initializing linked list
var list = new LinkedList(node1);

// showing output of the second node
console.log(list.head.next.value) // 4

Linked List Methods

Now that we are done with implementing the linked list, let us play or manipulate the linked list by implementing more methods to make use of the linked lists(helper methods):

The first helper method we will define is the size() method in the class LinkedList which will return the length of the linked list:

size=()=> {
    let count = 0;
    let node = this.head;
    // loop to iterate over linked list
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

In this code first, we are declaring a dummy variable count storing 0 in it and then storing the pointer of the head in the node variable. Then we declared a loop that will iterate over the linked list and increment the count variable.

The next helper method will be the getFirst() method where the head pointer will be returned:

getFirst=()=> {
    return this.head.value;
}

We can also get the last node of the linked list in the following manner:

getLast=()=> {
    let lastNode = this.head;
    if (lastNode) {
       while (lastNode.next) {
           lastNode = lastNode.next
       }
    }
    return lastNode.value
}

The whole code is now given below with showing the output of the second node value, size of linked list, first node value, and the last node value in the same order:

// creating node
class ListNode {
    constructor(value) {
        this.value = value
        this.next = null                
    }
}
// creating Linked List
class LinkedList {
    constructor(head = null) {
        this.head = head
    }
    size=()=> {
        let count = 0;
        let node = this.head;
        // loop to iterate over linked list
        while (node) {
            count++;
            node = node.next
        }
        return count;
    }

    getFirst=()=> {
        return this.head.value;
    }

    getLast=()=> {
        let lastNode = this.head;
        if (lastNode) {
            while (lastNode.next) {
                lastNode = lastNode.next
            }
        }
        return lastNode.value
    }
}

// initializing created nodes
var node1 = new ListNode(3);
var node2 = new ListNode(4);
node1.next = node2;

// initializing linked list
var list = new LinkedList(node1);

// showing output of the second node
console.log("Second node value: ",list.head.next.value) // 4
// showing size of the linked list
console.log("Size of Linked list: ",list.size());
// showing first node value
console.log("First node value: ",list.getFirst());
// showing last node value
console.log("Last node value: ",list.getLast());

Conclusion

After arrays, a linked list is the second most used data structure in any programming language. A linked list is like an array that stores a collection of different elements with the difference being that every element(node) of a linked list is an object containing a value of the element and a pointer pointing to the next node hence linking every element and the second difference is that the items aren’t saved in a specific memory location in a linked list.

In this post, we saw what linked lists are, the advantages and disadvantages of linked lists, the types of linked lists, and how to implement linked list data structure in JavaScript.

About the author

Shehroz Azam

A Javascript Developer & Linux enthusiast with 4 years of industrial experience and proven know-how to combine creative and usability viewpoints resulting in world-class web applications. I have experience working with Vue, React & Node.js & currently working on article writing and video creation.