Singly Linked List in JavaScript

Linked List 🔗 is a linear data structure that stores data as a list of nodes, where each node has a pointer to the next node and so on until the tail points to null. It has a head, tail, and length properties. We have arrays, but insertion/deletion or modification can be expensive while linked lists are efficient and dynamic.

|1|* --> |2| *--> |3| *--> null

Methods of a Linked List

isEmpty – Checks whether the linked list is empty.
peek – Returns the value of the head node without removing it.
push – Adds a new node with the specified value to the end of the list and returns the new length.
pop – Removes and returns the last node from the list.
shift – Removes and returns the first node from the list.
unshift – Adds a new node with the specified value to the beginning of the list and returns the new length.
get – Retrieves the node at a specified index.
set – Sets a new value for a node at a specified index and returns true if successful.
insert – Inserts a new node with a given value at a specified index in the list and returns true if successful.
remove – Removes the node at a specified index and returns it.
reverse – Reverses the order of nodes in the linked list.

JavaScript Code for a Singly Linked List

class Node {
    constructor(value) {
        this.value = value; // Data stored in the node
        this.next = null; // Pointer to the next node
    }
}

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

    // Checks if the list is empty
    isEmpty() {
        return this.length === 0;
    }

    // Returns the value of the head node
    peek() {
        return this.head?.value;
    }

    // Adds a new node with the given value to the end of the list
    push(value) {
        const newNode = new Node(value);
        if (this.isEmpty()) {
            // If the linkedList is empty, the new node becomes both the head and tail
            this.head = newNode;
            this.tail = newNode;
        } else {
            // Otherwise, add the new node to the end and update the 'tail' pointer
            this.tail.next = newNode;
            this.tail = newNode;
        }
        return ++this.length;
    }

    // Removes the last node from the list and returns it
    pop() {
        if (this.isEmpty()) return undefined;
        const oldTailNode = this.tail;
        if (this.length === 1) {
            // If the list has only one node
            this.head = null;
            this.tail = null;
        } else {
            // current keeps moving from head to tail to find last but one node
            let current = this.head;
            while (current.next !== this.tail) {
                current = current.next;
            }
            this.tail = current;
            this.tail.next = null;
        }
        this.length--;
        return oldTailNode;
    }

    // Removes the first node from the list and returns it
    shift() {
        if (this.isEmpty()) return undefined;
        const oldHeadNode = this.head
        this.head = oldHeadNode.next
        this.length--
        if (this.isEmpty()) {
            this.tail = null
        }
        return oldHeadNode
    }

    // Adds a new node with the given value to the beginning of the list
    unshift(value) {
        const newHeadNode = new Node(value);
        if (this.isEmpty()) {
            this.tail = newHeadNode
        } else {
            newHeadNode.next = this.head
        }
        this.head = newHeadNode
        return ++this.length;
    }

    // Retrieves the node at the specified index
    get(index) {
        if (index < 0 || index >= this.length) return undefined;
        let counter = 0
        let currentPointer = this.head
        while (counter !== index) {
            currentPointer = currentPointer.next
            counter++
        }
        return currentPointer
    }

    // Sets the value of the node at the specified index
    set(index, value) {
        const findNode = this.get(index)
        if (findNode) {
            findNode.value = value
            return true
        }
        return false
    }

    // Inserts a new node with the given value at the specified index
    insert(index, value) {
        if (index < 0 || index > this.length) return false;
        if (index === 0) {
            this.unshift(value)
            return true
        }
        if (index === this.length) {
            this.push(value)
            return true
        }
        const newNode = new Node(value)
        const beforeNode = this.get(index - 1)
        const afterNode = beforeNode.next
        beforeNode.next = newNode
        newNode.next = afterNode
        this.length++
        return true
    }

    // Removes the node at the specified index and returns it
    remove(index) {
        if (index < 0 || index >= this.length) return undefined;
        if (index === 0) {
            return this.shift()
        }
        if (index === this.length - 1) {
            return this.pop()
        }
        const beforeNode = this.get(index - 1)
        const nodeToBeRemoved = beforeNode.next
        beforeNode.next = nodeToBeRemoved.next
        this.length--
        return nodeToBeRemoved
    }

    // Reverses the order of nodes in the list
    reverse() {
        // Handle empty or single-node lists
        if (this.length <= 1) return this;
        /*
          In-place list reversal, we start from the head and move towards tail
          Order: Previous - Current - Next
          Next keeps moving ahead one by one
          Current sets the current node's next to Previous
          then Previous becomes Current and Current becomes Next
          and so on until Current is null i.e end of the list
        */
        let current = this.head
        let next = null
        let previous = null;
        while (current) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        this.head = this.tail
        // In the end current and next become null and previous is the last node
        this.tail = previous
        return this;
    }
}

Output

const myList = new SinglyLinkedList();

console.log(myList.isEmpty()); // true
myList.push(100);
myList.push(200);
myList.push(300);
console.log(myList.head);
/* {
    "value": 100,
    "next": {
        "value": 200,
        "next": {
            "value": 300,
            "next": null
        }
    }
} */

console.log(myList.length); // 3 - list length
console.log(myList.peek()); // 100 - value at head

console.log(myList.pop().value); // 300 - removed tail value
console.log(myList.shift().value); // 100 - removed head value
console.log(myList.peek()); // 200 - value at head

console.log(myList.length); // 1 - list length
console.log(myList.unshift(100)); // 2 (updated length)
console.log(myList.peek()); // 100 - value at head

console.log(myList.length); // 2 - list length
console.log(myList.get(0).value); // 100 - value at 0 index
console.log(myList.set(0, 1000)); // true - set value to 1000 at 0 index
console.log(myList.peek()); // 1000 - value at head

console.log(myList.insert(1, 150)); // true - inserted value at 1 index to 150
console.log(myList.head);
/* {
    "value": 1000,
    "next": {
        "value": 150,
        "next": {
            "value": 200,
            "next": null
        }
    }
} */
console.log(myList.remove(1).value); // 150 - Node removed

myList.push(300);
myList.push(400);
console.log(myList.head);
/* {
    "value": 1000,
    "next": {
        "value": 200,
        "next": {
            "value": 300,
            "next": {
                "value": 400,
                "next": null
            }
        }
    }
} */
console.log(myList.reverse().head);
/* {
    "value": 400,
    "next": {
        "value": 300,
        "next": {
            "value": 200,
            "next": {
                "value": 1000,
                "next": null
            }
        }
    }
} */

Time Complexity – O(n)

isEmpty() – O(1)
peek() – O(1)
push(value) – O(1)
pop() – O(n)
shift() – O(1)
unshift(value) – O(1)
get(index) – O(n)
set(index, value) – O(n)
insert(index, value) – O(n)
remove(index) – O(n)
reverse() – O(n)

Real World Applications

Web browsers use linked lists to track browsing history and navigation
Music players and various apps use linked lists for flexible playlist/order management.