How to implement a linked list in JavaScript

Key takeaways
A linked list consists of nodes, each containing a value and a reference to the next node, allowing dynamic size management compared to arrays.
Common operations include appending, prepending, inserting at specific indices, and deleting nodes.
Implement methods like toArray() to convert the linked list to an array for easier processing and display.
Enhance linked list functionality with methods for checking size, emptiness, and searching for nodes by value.

In JavaScript, creating a linked list is quite simple. A data structure called a linked list comprises a series of entries, each of which points to the element after it in the sequence. Linked lists are more dynamic and don’t have a set size like arrays.

Implementing linked lists with JavaScript classes

We will use two classes: the LinkedList class is used to manage the linked list, and Node class is used to represent individual list components. The LinkedList class has methods to search for nodes by value, delete nodes based on their value, append nodes to the end of the list, and convert the linked list to an array for simple manipulation and display.

Different operations for a linked list

We'll explore various operations that can be performed on a linked list using JavaScript classes. In this Answer, we'll delve into the details of appending nodes to extend the list, prepending nodes to add elements at the beginning, and deleting nodes based on their values.

Insertion

Let's look at how we are going to add a node in the linked list below:

// Node class
class Node {
  constructor(value) {
    this.value = value; 
    this.nextNode = null;
  }
}
// Linked List class
class LinkedList {
  constructor() {
    this.headNode = null; // The first node in the list
    this.tailNode = null; // The last node in the list
  }
  // Add a node at the end 
  append(value) {
    const newNode = new Node(value);
    if (!this.headNode) {
      this.headNode = newNode;
      this.tailNode = newNode;
    } else {
      this.tailNode.nextNode = newNode;
      this.tailNode = newNode;
    }
  }
  // Add a node at the start
  prepend(value) {
    const newNode = new Node(value);
    newNode.nextNode = this.headNode;
    this.headNode = newNode;
    if (!this.tailNode) {
      this.tailNode = newNode;
    }
  }
 // Add a node at a specified index
  insertAt(value, index) {
    if (index < 0) {
      throw new Error("Index out of bounds");
    }
    const newNode = new Node(value);
    if (index === 0) {
      this.prepend(value);
      return;
    }
    let currentNode = this.headNode;
    let currentIndex = 0;
    while (currentNode && currentIndex < index - 1) {
      currentNode = currentNode.nextNode;
      currentIndex++;
    }
    if (!currentNode) {
      throw new Error("Index out of bounds");
    }
    newNode.nextNode = currentNode.nextNode;
    currentNode.nextNode = newNode;
    if (!newNode.nextNode) {
      this.tailNode = newNode;
    }
  }
  // Convert a linked list to JS array 
  toArray() {
    const resultArray = [];
    let currentNode = this.headNode;
    while (currentNode) {
      resultArray.push(currentNode.value);
      currentNode = currentNode.nextNode;
    }
    return resultArray;
  }
}
// Example usage
const customList = new LinkedList();
customList.append(100);
customList.append(200);
customList.append(300);
console.log("original linkedlist");
console.log(customList.toArray()); // Output: [100, 200, 300]
customList.append(400);
console.log("element added at the end");
console.log(customList.toArray()); // Output: [100, 200, 300, 400]
customList.prepend(50);
console.log("element added at node 0");
console.log(customList.toArray()); // Output: [50, 100, 200, 300, 400]
customList.insertAt(150, 2);
console.log("Element added at index 2:");
console.log(customList.toArray()); // Output: [50, 100, 150, 200, 300, 400]

Code explanation

Let's break down the code written above:

Lines 2–7: We are defining a Node class. Each Node has two properties: value to store the actual data and nextNode to reference the next node in the sequence. Initially, nextNode is set to null.
Line 10: We are defining and creating a LinkedList class with multiple methods. It is one of the main classes and it manages the nodes, allowing you to create, modify, and traverse the list.
Lines 11–14: The LinkedList class has a constructor that initializes two properties: headNode and tailNode. These properties represent the first and last nodes of the list, respectively. Initially, when a linked list is created, both headNode and tailNode are set to null, indicating an empty list.
Line 17: We define an append method. The append(value) method is used to add a new node to the end of the linked list. It creates a new Node with the provided value.
Lines 19–21: If the list is empty (i.e., headNode is null), the new node becomes both the headNode and the tailNode.
Lines 22–25: If the list is not empty, the new node is linked to the current tailNode and the tailNode is updated to the new node.
Line 29: We define the prepend method. The prepend(value) method adds a new node to the beginning of the linked list.
Line 30: It creates a new newNode with the provided value.
Lines 31–32: The new node is linked to the current headNode and then it becomes the new headNode.
Lines 33–35: If the list was empty, the new node also becomes the tailNode.
Lines 38–69: We are writing a function InsertAt to insert at a specific index in our linked list.
Lines 40–42: We first check if the provided index is less than 0. If it is, it throws an error because the index is out of bounds.
Lines 46–48: If the index is 0, it calls the prepend method to add the node at the beginning of the list.
Lines 51–57: Then we initialize currentNode to headNode and currentIndex to 0. Then, it iterates through the list to find the node just before the specified index.
Lines 59–61: After the loop, if currentNode is null, it means the index was out of bounds and it throws an error.
Lines 63–64: The nextNode property of the new node is set to the node currently at the specified index. Then, the nextNode property of the node at index - 1 is updated to the new node.
Lines 66–68: If the new node is inserted at the end of the list, update the tailNode to be the new node.

Deleting a node

Let's look at how we are going to delete an element from the linked list below:

// Node class
class Node {
  constructor(value) {
    this.value = value; 
    this.nextNode = null;
  }
}
// Linked List class
class LinkedList {
  constructor() {
    this.headNode = null; // The first node in the list
    this.tailNode = null; // The last node in the list
  }
  // Add a node at the end 
  append(value) {
    const newNode = new Node(value);
    if (!this.headNode) {
      this.headNode = newNode;
      this.tailNode = newNode;
    } else {
      this.tailNode.nextNode = newNode;
      this.tailNode = newNode;
    }
  }
  // Add a node at the start
  prepend(value) {
    const newNode = new Node(value);
    newNode.nextNode = this.headNode;
    this.headNode = newNode;
    if (!this.tailNode) {
      this.tailNode = newNode;
    }
  }
  // Delete a node
  delete(value) {
    if (!this.headNode) {
      return;
    }
    if (this.headNode.value === value) {
      this.headNode = this.headNode.nextNode;
      if (!this.headNode) {
        this.tailNode = null;
      }
      return;
    }
    let currentNode = this.headNode;
    while (currentNode.nextNode) {
      if (currentNode.nextNode.value === value) {
        currentNode.nextNode = currentNode.nextNode.nextNode;
        if (!currentNode.nextNode) {
          this.tailNode = currentNode;
        }
        return;
      }
      currentNode = currentNode.nextNode;
    }
  }
  // Convert a linked list to JS array 
  toArray() {
    const resultArray = [];
    let currentNode = this.headNode;
    while (currentNode) {
      resultArray.push(currentNode.value);
      currentNode = currentNode.nextNode;
    }
    return resultArray;
  }
}
// Example usage
const customList = new LinkedList();
customList.append(100);
customList.append(200);
customList.append(300);
customList.prepend(50);
console.log("original linkedlist");
console.log(customList.toArray()); // Output: [50, 100, 200, 300]
customList.delete(200);
console.log(customList.toArray()); // Output: [50, 100, 300]

Line 39: We create the delete method. The delete(value) method removes a node with the specified value from the linked list.
Lines 40–42: It first checks if the list is empty (i.e., head is null) and, if so, returns without any action.
Lines 43–49: If the node to be deleted is the headNode, it simply updates the headNode to the next node. If the node to be deleted is also the tailNode, it updates the tailNode.
Lines 50–60: It iterates through the list, finds the node to delete, and updates the next reference of the previous node to skip the node to be deleted. Lines 54–56 are responsible for updating the tailNode reference when deleting a node from the linked list.
Line 76: We define a toArray method. The toArray() method converts the linked list into a regular JavaScript array for easy display or further processing.
Lines 79–84: These iterate through the list and collect the value from each node in an array.

Other operations

Let's look at some of the other operations, like getSize(), isEmpty() and find node by its value from the linked list below:

// Node class
class Node {
  constructor(value) {
    this.value = value;
    this.nextNode = null;
  }
}
// Linked List class
class LinkedList {
  constructor() {
    this.headNode = null; // The first node in the list
    this.tailNode = null; // The last node in the list
    this.size = 0; // Initialize size to 0
  }
  // Add a node at the end
  append(value) {
    const newNode = new Node(value);
    if (!this.headNode) {
      this.headNode = newNode;
      this.tailNode = newNode;
    } else {
      this.tailNode.nextNode = newNode;
      this.tailNode = newNode;
    }
    this.size++; // Increment size
  }
  // Convert a linked list to JS array
  toArray() {
    const resultArray = [];
    let currentNode = this.headNode;
    while (currentNode) {
      resultArray.push(currentNode.value);
      currentNode = currentNode.nextNode;
    }
    return resultArray;
  }
  // Get the size of the linked list
  getSize() {
    return this.size;
  }
  // Check if the linked list is empty
  isEmpty() {
    return this.size === 0;
  }
  // Find a node by its value
  find(value) {
    let currentNode = this.headNode;
    while (currentNode) {
      if (currentNode.value === value) {
        return currentNode;
      }
      currentNode = currentNode.nextNode;
    }
    return null;
  }
}
// Example usage
const customList = new LinkedList();
customList.append(100);
customList.append(200);
customList.append(300);
console.log("Original linked list:");
console.log(customList.toArray()); // Output: [100, 200, 300]
console.log("Size of the linked list:", customList.getSize()); // Output: 3
console.log("Is the linked list empty?", customList.isEmpty()); // Output: false
const foundNode = customList.find(150);
console.log("Found node:", foundNode ? foundNode.value : "Node not found"); // Output: Node not found

Lines 42–44: We are returning the size of the linked list.
Lines 47–49: We are checking whether the linked list is empty. If it is empty, then we are returning false.
Lines 52–62: We are finding a node by its value. If the value exists in the linked list, then we return "Found node"; otherwise, it returns "Node not found”.

Conclusion

Implementing a linked list in JavaScript provides a fundamental understanding of data structures and their manipulation. By leveraging classes to manage nodes and perform operations like appending, prepending, and deleting, developers can create efficient and flexible data structures tailored to their specific needs.

Free Resources