How to implement LinkedList in Javascript in 2023?

In this article, we will be seeing how to implement LinkedList in javascript and various operations of it.

Note: I have chosen Javascript language (my favorite) to implement it, language is just a medium here, we can implement it in any programming language. The key Idea is the underlying algorithm will always remain the same.

Before we dive into the coding part, let’s start with the definition of the Linked List.

What is Linked List?

Def 1 —

A linked list is a linear data structure where elements are considered as a node that stores data and a pointer to the next node i.e element.

Def 2 —

A linked list is a linear data structure where elements are not stored at a contiguous memory location.

Contiguous memory allocation provides random access i.e direct access.

Since array elements are stored in this fashion so accessing any element takes constant time i.e O(1) whereas for the linked list to access any element we have to follow the pointer so it is a sequential access and takes O(n) time.

Array vs Linked List

Accessing ith element
1. Array → O(1)
2. LinkedList → O(n)
Insertion & deletion
1. Array → O(n)
2. Single Linked List → O(n)
3. Doubly linked list → O(1)
Size
1. Array → fixed
2. Linked List → dynamic

Linked list Operation

Traversal
Size of the linked list
Insertion
Deletion
Searching

Implement Linked List in Javascript

Let’s define the constructor function for the Node i.e element of the linked list —

				
					function Node(data) {
    this.data = data;
    this.next = null;
}

Now, we can define the Linked List constructor —

				
					function LinkedList() {}

Let’s add a create function in the prototype of the linked list which will take an array of elements and create the linked list.

				
					LinkedList.prototype.create = function (arr) {
    
    let head = new Node(arr[0]);
    let temp = head;
    
    for (let i = 1; i < arr.length; i++) {
        temp.next = new Node(arr[i]);
        temp = temp.next;
    }
    
    // returning head of the linked list
    return head;
}

That’s it, LinkedList is created 😊

Let’s implement each of the primitive operations.

Traverse the linked list

Start from the head node and traverse till the end of the list.

				
					LinkedList.prototype.traverse = function (head) {
    
    let temp = head;
    
    while (temp != null) {
        console.log(temp.data);
        temp = temp.next;
    }
}

TC: O(n)

Size of the linked list

Returns the count of all elements in the linked list.

				
					LinkedList.prototype.size = function (head) {
    
    let temp = head;
    let count = 0;
    
    while (temp != null) {
        count++;
        temp = temp.next;
    }
    
    return count;
}

TC: O(n)

Insertion in the linked list

Insert the element in the linked list at the kth index and returns the updated head.

				
					LinkedList.prototype.insert = function (head, k, elem) {
    
    let size = this.size(head);    
   
    // case 1. if index k is not valid
    if (k < 0 || k > size) {
        return head;
    }
    
    let newNode = new Node(elem);
    
    // case 2. insert at beginning
    if (k === 0) {
        newNode.next = head;
        return newNode;
    }
    
    // case 3. insert at kth node
    let temp = head;
  
    for (let i = 0; i < k - 1; i++) {
        temp = temp.next;
    }
  
    newNode.next = temp.next;
    temp.next = newNode;
  
    return head;
}

TC: O(n)

Deletion in the linked list

Delete the kth index element from the linked list and returns the updated head

				
					LinkedList.prototype.delete = function (head, k) {
    
    let size = this.size(head);    
   
    // case 1. if index k is not valid
    if (k < 0 || k > size) {
        return head;
    }
    
    // case 2. deletion at the beginning
    let temp = head;
    
    if (k === 0) {
        temp = head.next;
        head.next = null;
        return temp;
    }
    
    // case 3. delete kth node
    temp = head;
  
    for (let i = 0; i < k - 1; i++) {
        temp = temp.next;
    }
    
    let cur = temp.next; // element to be deleted
    temp.next = temp.next.next; // or cur.next (both are fine)
    cur.next = null;
  
    return head;
}

TC: O(n)

Searching in the linked list

Given the head of the linked list and an element, search for the element in the list.

				
					LinkedList.prototype.search = function (head, elem) {

    let temp = head;
    let isFound = false;
    
    while (temp != null) {
        
        if (temp.data === elem) {
            isFound = true;
            break;
        }
        
        temp = temp.next;
    }
    
    return isFound;
}

TC: O(n)