Linked List Implementation in JavaScript

Linked lists represent one of the most essential data structures in computer science. In the upcoming sections, we will examine the various types of linked lists, followed by an implementation of linked lists in JavaScript. By the conclusion of this article, you will gain a solid understanding of linked lists and feel assured in your ability to utilize them in your coding endeavors.

What is a Linked List?

A Linked List serves as a linear data structure in which data elements are held at non-adjacent memory locations, with elements interconnected through pointers (a pointer is a variable that stores a memory address). Each node consists of two components:

• ✅ Data: The information that resides within a node.
• ✅ Pointer: Points to the subsequent node in the sequence (or null if it represents the final node).

In contrast to arrays, linked lists do not reserve memory in adjacent blocks. Rather, each node contains a reference to the subsequent node, forming a sequential arrangement. This characteristic allows linked lists to expand or contract in size without the necessity of relocating any elements in memory, which enhances their flexibility.

Types of Linked Lists

There are several types of linked lists, each designed for specific applications. In this section, we will explore the three primary categories of linked lists, along with their explanations and accompanying code examples.

Singly Linked List

In a singly linked list, every node contains a reference to the subsequent node. Each node in the list is composed of two data elements along with a connection to the following node. The pointer located in the last node directs to null, signifying the conclusion of the list.

Attributes:

• ✅ Unidirectional (can only be traversed in a single direction).
• ✅ Easy to implement.

JavaScript Implementation:

Code:

Example

class Node {
    constructor(data) {
      this.data = data;
      this.next = null;
    }
  }
  
  class SinglyLinkedList {
    constructor() {
      this.head = null;
    }
  
    append(data) {
      const newNode = new Node(data);
      if (!this.head) {
        this.head = newNode;
        return;
      }
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  
    display() {
      let current = this.head;
      while (current) {
        console.log(current.data);
        current = current.next;
      }
    }
  }
  
  const list = new SinglyLinkedList();
  list.append(10);
  list.append(20);
  list.append(30);
  list.display();

Output:

10
20
30

Doubly Linked List

Doubly linked list is the enhanced version of the singly linked list with the additional pointer. Each Node comprises three components:

• ✅ Data
• ✅ A pointer to the next node
• ✅ Pointer for the previous node

Features:

• ✅ Allows bidirectional navigation (capable of moving both forwards and backwards).
• ✅ Offers greater flexibility, though it requires extra memory for the additional pointer.

JavaScript Implementation:

Code:

Example

class DoublyNode {
    constructor(data) {
      this.data = data;
      this.next = null;
      this.prev = null;
    }
  }
  
  class DoublyLinkedList {
    constructor() {
      this.head = null;
      this.tail = null;
    }
  
    append(data) {
      const newNode = new DoublyNode(data);
      if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
        return;
      }
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  
    displayForward() {
      let current = this.head;
      while (current) {
        console.log(current.data);
        current = current.next;
      }
    }
  
    displayBackward() {
      let current = this.tail;
      while (current) {
        console.log(current.data);
        current = current.prev;
      }
    }
  }
  
  const dList = new DoublyLinkedList();
  dList.append(10);
  dList.append(20);
  dList.append(30);
  dList.displayForward();
  dList.displayBackward();

Output:

10
20
30
30
20
10

Circular Linked List

In a circular linked list, rather than having a null reference at the final node, it refers back to the initial node, forming a circular structure. Similar to other linked lists, circular linked lists can be either unidirectional (singly linked) or bidirectional (doubly linked).

Attributes:

• ✅ The collection does not contain any null references.
• ✅ Ideal for scenarios that require a circular iteration (such as round-robin scheduling).

JavaScript Implementation (Singly Circular):

Code:

Example

class CircularNode {
    constructor(data) {
      this.data = data;
      this.next = null;
    }
  }
  
  class CircularLinkedList {
    constructor() {
      this.head = null;
    }
  
    append(data) {
      const newNode = new CircularNode(data);
      if (!this.head) {
        this.head = newNode;
        newNode.next = this.head;
        return;
      }
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next;
      }
      current.next = newNode;
      newNode.next = this.head;
    }
  
    display() {
      if (!this.head) return;
      let current = this.head;
      do {
        console.log(current.data);
        current = current.next;
      } while (current !== this.head);
    }
  }
  
  const cList = new CircularLinkedList();
  cList.append(10);
  cList.append(20);
  cList.append(30);
  cList.display();

Output:

10
20
30

Key Differences between Linked Lists and Arrays

Advantages of Linked Lists

• ✅ Dynamic Size: A linked list has a dynamic size unlike an array, which is of fixed size.
• ✅ Efficient Insertions/Deletions: It requires only O(1) time complexity for inserting or deleting from the head/ tail of a linked list, because we only need to change some pointers by adding and removing from the list.
• ✅ Memory Utilization: Since linked lists don’t need contiguous blocks of memory, they can be used for dynamic memory allocation.
• ✅ Ease of Implementation for Queues/Stacks: Linked lists can be used in the implementation of other data structures like queues and stacks.

Disadvantages of Linked Lists

• ✅ Sequential Access: Elements in a linked list are accessed by starting at the head node and its complexity is (O(n)) whereas elements in an array are accessed randomly and it have the complexity (O(1)).
• ✅ Memory Overhead: Each node contains an extra pointer/reference, making it more memory-intensive than arrays.
• ✅ Complex Operations: Accessing, searching or traversing the list is slower and more complex than Arrays.
• ✅ Cache Performance: The elements of a linked list are scattered randomly throughout memory, leading to poor cache performance.

Conclusion

Linked lists represent a highly adaptable and dynamic data structure that forms the foundational elements for various advanced algorithms and systems. Although they require additional memory for pointers and exhibit slower access times compared to arrays, their dynamic nature renders them particularly effective in scenarios where elements are frequently added or removed. Consequently, gaining proficiency in singly, doubly, and circular linked lists can significantly enhance the development of applications in a highly efficient and resilient manner using JavaScript.