How to Implement a Linked List in JavaScript

Linked List is a linear data structure of nodes connected with pointers. Linked lists, on the other hand, operate in disjoint memory regions, as opposed to arrays, which must place their elements in order. There is no data shifting, so adding and removing parts is also faster. On the other hand, linked lists require more space than arrays, since each element has a pointer to the next one.

Advantages of Linked Lists Over Arrays.

Below are the advantages of array.

Dynamic Size: They can dynamically grow and shrink unlike arrays whose size is fixed.
Fast Insertion and Deletion: While inserting or deleting elements from array takes O(n) time due to shift of elements, linked list allows the O(1) insertion and deletion time for elements at the beginning or middle.
Optimal Memory Usage: Unlike dynamic arrays, linked lists don't need to be resized, and therefore, it does not waste any preallocated memory.

Use Cases for Linked lists
To initialize stacks, queues and graphs.
A fast data structure for regular insertions and deletions.
Undo/redo commands in apps.

Understanding Linked Lists.

A linked list is made up of nodes, which stores data that represents its content, as well as a pointer called 'next' that links to the next node in the sequence.

Types of Linked Lists

Below are types of Linked lists:

Singly Linked List: Each node points to the next node, resulting in a one-directional chain.
Doubly Linked List: Each node holds pointers for the next node and previous node.
Circular Linked List : Last node points to the first node.

What is a Node Class?

It is the main unit of linked list. It contains the value and next node reference.

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

This class initializes a node with value and a next pointer set to null.

Implementing a Singly Linked List

Now, let's create a LinkedList class with basic operations.

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

    // Append a node at the end
    append(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }

    // Prepend a node at the beginning
    prepend(value) {
        const newNode = new Node(value);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }

    // Insert a node at a specific position
    insertAt(index, value) {
        if (index < 0 || index > this.size) return;
        const newNode = new Node(value);
        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let current = this.head;
            let prev = null;
            let count = 0;
            while (count < index) {
                prev = current;
                current = current.next;
                count++;
            }
            prev.next = newNode;
            newNode.next = current;
        }
        this.size++;
    }

    // Remove a node at a specific position
    removeAt(index) {
        if (index < 0 || index >= this.size) return;
        let current = this.head;
        if (index === 0) {
            this.head = current.next;
        } else {
            let prev = null;
            let count = 0;
            while (count < index) {
                prev = current;
                current = current.next;
                count++;
            }
            prev.next = current.next;
        }
        this.size--;
    }

    // Find a node by value
    find(value) {
        let current = this.head;
        while (current) {
            if (current.value === value) return true;
            current = current.next;
        }
        return false;
    }

    // Print the list
    printList() {
        let current = this.head;
        let result = '';
        while (current) {
            result += current.value + ' -> ';
            current = current.next;
        }
        console.log(result + 'null');
    }
}

Implementing a Doubly Linked List

Doubtly linked lists contain an additional pointer, prev.

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

The LinkedList class has to be edited to maintain both next and prev pointers.

Implementing a Circular Linked List

A Circular Linked List connects the last node back to the first.

class CircularLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    append(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            this.tail.next = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
            this.tail.next = this.head;
        }
    }
}

Real-World Applications of Linked Lists

Browsing History: Implemented as a doubly linked list.
Undo/Redo function: Used in text editors.
Schedulers: Round-robin scheduling uses circular linked lists.

Conclusion

This article is all about linked lists, their types, and their implementation in JavaScript. Singly, doubly, and circular linked lists were looked at, along with some key operations. Understanding linked lists is a must if you want to tackle data structures and optimize algorithms well.