javascriptroom blog

Implementation of LinkedList in JavaScript

In the world of data structures, LinkedLists are a fundamental and versatile concept. A LinkedList is a linear data structure where each element is a separate object, known as a node. Each node contains two main components: data (the value it holds) and a reference (or pointer) to the next node in the sequence. Unlike arrays, LinkedLists do not have a fixed size and can grow or shrink dynamically.

JavaScript, being a high - level programming language, does not have a built - in LinkedList data type like some other languages. However, we can implement a LinkedList using JavaScript objects and functions. This blog post will guide you through the step - by - step implementation of a LinkedList in JavaScript, covering common operations, best practices, and example usage.

2026-07

Table of Contents#

  1. Understanding LinkedList Basics
  2. Node Structure
  3. Implementing a Singly LinkedList
    • Creating the LinkedList Class
    • Adding Nodes
    • Removing Nodes
    • Searching for a Node
    • Traversing the LinkedList
  4. Best Practices for LinkedList Implementation
  5. Example Usage
  6. Conclusion
  7. References

1. Understanding LinkedList Basics#

A LinkedList is a collection of nodes that are connected to each other. There are two main types of LinkedLists: singly and doubly. In a singly LinkedList, each node has a reference to the next node in the list. In a doubly LinkedList, each node has references to both the next and the previous nodes.

The first node of a LinkedList is called the head, and the last node is called the tail. If the list is empty, the head (and tail) points to null.

Advantages of LinkedLists#

  • Dynamic size: LinkedLists can grow or shrink during runtime, unlike arrays which have a fixed size.
  • Efficient insertion and deletion: Inserting or deleting a node in a LinkedList can be done in constant time O(1) (in most cases) if we have a reference to the node where the operation is to be performed.

Disadvantages of LinkedLists#

  • Random access is slow: Unlike arrays, we cannot directly access an element at a particular index in a LinkedList. We have to traverse the list from the head until we reach the desired node, which takes linear time O(n).

2. Node Structure#

The basic building block of a LinkedList is the node. Let's create a simple Node class in JavaScript:

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

In this code, the Node class has a constructor that takes a value as an argument. The value property holds the data of the node, and the next property is initially set to null, which means it doesn't point to any other node yet.

3. Implementing a Singly LinkedList#

Creating the LinkedList Class#

We will now create a LinkedList class that will manage the nodes in the list.

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

In the constructor of the LinkedList class, we initialize three properties:

  • head: Points to the first node in the list. Initially, it is set to null because the list is empty.
  • tail: Points to the last node in the list. Initially, it is set to null.
  • length: Keeps track of the number of nodes in the list. Initially, it is set to 0.

Adding Nodes#

There are two common ways to add nodes to a LinkedList: at the beginning (prepend) and at the end (append).

Prepend#

class LinkedList {
    //... previous code...
 
    prepend(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

In the prepend method, we first create a new node. If the list is empty, the new node becomes both the head and the tail. Otherwise, we set the next pointer of the new node to the current head and then update the head to point to the new node. Finally, we increment the length of the list.

Append#

class LinkedList {
    //... previous code...
 
    append(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
}

In the append method, we create a new node. If the list is empty, the new node becomes both the head and the tail. Otherwise, we set the next pointer of the current tail to the new node and then update the tail to point to the new node. Finally, we increment the length of the list.

Removing Nodes#

We can also remove nodes from the LinkedList. Let's implement a method to remove the first node (shift) and the last node (pop).

Shift#

class LinkedList {
    //... previous code...
 
    shift() {
        if (!this.head) return undefined;
        const currentHead = this.head;
        this.head = this.head.next;
        if (!this.head) {
            this.tail = null;
        }
        this.length--;
        return currentHead;
    }
}

In the shift method, we first check if the list is empty. If it is, we return undefined. Otherwise, we store the current head in a variable, update the head to point to the next node, and decrement the length. If the list becomes empty after the operation, we also set the tail to null.

Pop#

class LinkedList {
    //... previous code...
 
    pop() {
        if (!this.head) return undefined;
        let current = this.head;
        let newTail = current;
        while (current.next) {
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        if (this.tail === this.head) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail.next = null;
        }
        this.length--;
        return current;
    }
}

In the pop method, we first check if the list is empty. If it is, we return undefined. Otherwise, we use two pointers (current and newTail) to traverse the list. When we reach the end of the list, current points to the last node, and newTail points to the second - last node. We update the tail to newTail, set the next pointer of the new tail to null, and decrement the length. If the list becomes empty, we set both the head and the tail to null.

Searching for a Node#

We can search for a node with a specific value in the LinkedList.

class LinkedList {
    //... previous code...
 
    find(value) {
        if (!this.head) return null;
        let current = this.head;
        while (current) {
            if (current.value === value) {
                return current;
            }
            current = current.next;
        }
        return null;
    }
}

In the find method, we start from the head and traverse the list until we find a node with the given value or reach the end of the list. If the node is found, we return it; otherwise, we return null.

Traversing the LinkedList#

We can traverse the LinkedList and print the values of all the nodes.

class LinkedList {
    //... previous code...
 
    printList() {
        const values = [];
        let current = this.head;
        while (current) {
            values.push(current.value);
            current = current.next;
        }
        console.log(values.join(' -> '));
    }
}

In the printList method, we start from the head and traverse the list, pushing the values of each node into an array. Finally, we join the array elements with an arrow (->) and print the result.

4. Best Practices for LinkedList Implementation#

  • Always handle edge cases: Make sure to handle cases like an empty list when performing operations such as adding, removing, or searching for nodes.
  • Use descriptive variable names: Use variable names that clearly indicate their purpose, such as current, newNode, etc.
  • Keep track of the length: Maintaining a length property can make it easier to check the size of the list and perform operations that depend on the size.

5. Example Usage#

// Create a new LinkedList
const list = new LinkedList();
 
// Append some nodes
list.append(1);
list.append(2);
list.append(3);
 
// Print the list
list.printList(); // Output: 1 -> 2 -> 3
 
// Prepend a node
list.prepend(0);
list.printList(); // Output: 0 -> 1 -> 2 -> 3
 
// Remove the first node
list.shift();
list.printList(); // Output: 1 -> 2 -> 3
 
// Remove the last node
list.pop();
list.printList(); // Output: 1 -> 2
 
// Search for a node
const node = list.find(2);
console.log(node ? node.value : 'Node not found'); // Output: 2

6. Conclusion#

In this blog post, we have learned how to implement a singly LinkedList in JavaScript. We covered the basic concepts of LinkedLists, the node structure, and various operations such as adding, removing, searching, and traversing nodes. By following the best practices, you can create a robust and efficient LinkedList implementation. LinkedLists are a powerful data structure that can be used in many scenarios, such as implementing stacks, queues, and other complex data structures.

7. References#