A Complete Guide to Singly and Doubly Linked Lists in JavaScript

Linked lists are fundamental data structures in computer science. They offer dynamic memory allocation, efficient insertion, and deletion of elements compared to arrays. This guide will walk you through implementing Singly Linked Lists and Doubly Linked Lists in JavaScript, focusing on core functionalities like managing the head, tail, and size of the list.

---

1. What is a Linked List?

A linked list is a linear data structure consisting of nodes. Each node contains:

1. Data: The value of the node.

2. Pointer: A reference to the next node (and optionally the previous node in doubly linked lists).

Types of Linked Lists:

• Singly Linked List (SLL): Each node points to the next node.

• Doubly Linked List (DLL): Each node points to both the next and previous nodes.

---

2. Singly Linked List (SLL)

Structure of an SLL:

• Head: Points to the first node.

• Tail: Points to the last node.

• Size: Tracks the number of nodes in the list.

Core Operations in SLL:

1. Insert at Head

2. Insert at Tail

3. Remove a Node

4. Search for a Value

JavaScript Implementation:

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

class SinglyLinkedList {
  constructor() {
    this.head = null;  // Points to the first node
    this.tail = null;  // Points to the last node
    this.size = 0;     // Tracks the size of the list
  }

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

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

  // Remove the first occurrence of a value
  remove(value) {
    if (!this.head) return null;

    if (this.head.value === value) {
      this.head = this.head.next;
      this.size--;
      return;
    }

    let current = this.head;
    while (current.next && current.next.value !== value) {
      current = current.next;
    }

    if (current.next) {
      current.next = current.next.next;
      if (!current.next) this.tail = current;
      this.size--;
    }
  }

  // Display the linked list
  display() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" -> "));
  }
}

// Example Usage
const sll = new SinglyLinkedList();
sll.append(10);
sll.append(20);
sll.prepend(5);
sll.display(); // Output: 5 -> 10 -> 20
sll.remove(10);
sll.display(); // Output: 5 -> 20

---

3. Doubly Linked List (DLL)

Structure of a DLL:

• Head: Points to the first node.

• Tail: Points to the last node.

• Size: Tracks the number of nodes in the list.

• Previous Pointer: Points to the previous node.

Core Operations in DLL:

1. Insert at Head

2. Insert at Tail

3. Remove a Node

4. Search for a Value

JavaScript Implementation:

class DoublyNode {
  constructor(value) {
    this.value = value; // Data of the node
    this.next = null;  // Pointer to the next node
    this.prev = null;  // Pointer to the previous node
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;  // Points to the first node
    this.tail = null;  // Points to the last node
    this.size = 0;     // Tracks the size of the list
  }

  // Add a node at the end (tail)
  append(value) {
    const newNode = new DoublyNode(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  // Add a node at the beginning (head)
  prepend(value) {
    const newNode = new DoublyNode(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.size++;
  }

  // Remove the first occurrence of a value
  remove(value) {
    if (!this.head) return null;

    if (this.head.value === value) {
      this.head = this.head.next;
      if (this.head) this.head.prev = null;
      else this.tail = null;
      this.size--;
      return;
    }

    let current = this.head;
    while (current && current.value !== value) {
      current = current.next;
    }

    if (current) {
      if (current.next) current.next.prev = current.prev;
      if (current.prev) current.prev.next = current.next;
      if (current === this.tail) this.tail = current.prev;
      this.size--;
    }
  }

  // Display the linked list
  display() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" <-> "));
  }
}

// Example Usage
const dll = new DoublyLinkedList();
dll.append(10);
dll.append(20);
dll.prepend(5);
dll.display(); // Output: 5 <-> 10 <-> 20
dll.remove(10);
dll.display(); // Output: 5 <-> 20

---

4. Key Differences Between SLL and DLL

---

5. Use Cases of Linked Lists

• Singly Linked List:

  • Implementing stacks and queues.

  • Managing dynamic collections like menus or breadcrumbs.

• Doubly Linked List:

  • Undo/Redo functionality.

  • Managing playlists or browser history.

---

This guide provides the building blocks for working with linked lists in JavaScript. Whether you're preparing for interviews or working on real-world applications, understanding linked lists is a valuable skill for efficient data management. Happy coding!