Linked List

A linked list is a linear data structure consisting of a sequence of connected nodes, where each node contains two parts: the data and a reference (or pointer) to the next node in the sequence.

Every linked list starts with a special reference called the HEAD, which points to the first node in the list. The last node is identified by its next pointer being set to NULL, indicating the end of the list.

There are different types of linked lists: singly, doubly, and circular. In this article, we'll focus on the singly linked list.

Note: You might have played the game Treasure Hunt, where each clue includes the information about the next clue. That is how the linked list operates.

Linked List Overview

A Linked List is a linear data structure where each element (called a node) contains:

• data: the actual value

• next: a reference (or pointer) to the next node in the list

In this implementation, we use a singly linked list, meaning each node points only to the next one.

Structure of the Code

1. Node Class

class Node {
  constructor(data) {
    this.data = data; // value of the node
    this.next = null; // pointer to the next node (initially null)
  }
}

2. LinkedList Class

class LinkedList {
  constructor() {
    this.head = null; // first node of the list
    this.size = 0;    // keeps track of total elements
  }
}

Functionality Explained

1. addElement(element)

• Adds a new element at the end of the list.

• If the list is empty (this.head is null), the new node becomes the head.

• Otherwise, it traverses the list until the last node and appends the new node.

2. insertAt(element, index)

• Inserts a new element at a specific position (index).

• Handles inserting at the beginning (index === 0).

• Traverses to the correct position and inserts the node between prev and curr.

3. removeELement(element)

• Removes the first occurrence of the element from the list.

• If the element is the head, it updates this.head.

• Otherwise, it traverses the list to find and remove the node.

• Decrements size on successful removal.

4. getSize()

• Simply logs the size of the list.

const linkedlist = new LinkedList();
linkedlist.addElement(2);  // List: 2
linkedlist.addElement(4);  // List: 2 -> 4
linkedlist.addElement(6);  // List: 2 -> 4 -> 6

linkedlist.removeELement(6); // List after removal: 2 -> 4

linkedlist.insertAt(3, 1); // List: 2 -> 3 -> 4
linkedlist.getSize();      // size: 3

Linked List code :

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

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

  addElement(element) {
    const node = new Node(element);

    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }

    this.size++;
  }

  insertAt(element, index) {
    if (index < 0 || index > this.size) {
      return "please enter valid index";
    } else {
      let node = new Node(element);

      let curr, prev;

      // curr = this.head;

      if (index === 0) {
        node.next = this.head;
        this.head = node;
      } else {
        curr = this.head;
        let it = 0;

        while (it < index) {
          it++;
          prev = curr;
          curr = curr.next;
        }

        node.next = curr;
        prev.next = node;
      }
      this.size++;
    }
  }

  removeELement(element) {
    if (!this.head) {
      console.log("List is empty");
      return;
    }

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

    let current = this.head;
    let prev = null;

    while (current && current.data !== element) {
      prev = current;
      current = current.next;
    }

    if (current && current.data === element) {
      prev.next = current.next;
      this.size--;
    } else {
      console.log("element not found");
    }
  }

  getSize() {
    console.log("size :", this.size);
  }
}

const linkedlist = new LinkedList();
linkedlist.addElement(2);
linkedlist.addElement(4);
linkedlist.addElement(6);

linkedlist.getSize();
console.log(linkedlist.head);
linkedlist.removeELement(6);
linkedlist.insertAt(3, 1);

Linked list Complexities

Space Complexity: O(n)

Applications of Linked Lists

1. Dynamic Memory Allocation

• Linked lists allocate memory as needed, making them ideal for systems with constrained or dynamic memory requirements.

2. Implementation of Stack and Queue

• Singly linked lists are used to implement stacks (LIFO), and doubly linked lists or circular linked lists can be used for queues (FIFO).

3. Undo/Redo Functionality in Software

• Doubly linked lists are used to track history in editors and applications to implement undo and redo operations.

4. Hash Tables (with Chaining)

• In separate chaining for collision resolution, each bucket is implemented as a linked list.

5. Graphs (Adjacency List Representation)

• Each vertex in a graph can store a linked list of its adjacent vertices.

6. Navigation Systems / Browser History

• Doubly linked lists are used to move forward and backward efficiently between pages or routes.

7. Music and Video Playlists

• Songs or videos are linked such that users can skip forward or backward.

8. Image Viewer

• Viewing images in a slideshow allows navigating to the previous or next image, commonly using doubly linked lists.

9. Polynomial Arithmetic

• Terms of polynomials are stored as nodes in a linked list to facilitate operations like addition or multiplication.

10. Memory Management in Operating Systems

• Free blocks of memory can be maintained using a linked list for efficient allocation and deallocation.

11. Multilevel Data Structures

• Structures like skip lists and adjacency matrices can use linked lists internally.

12. Job Scheduling

• Tasks can be queued using a linked list structure in real-time operating systems.

13. Big Integer Arithmetic

• For operations on very large integers, digits can be stored in nodes of a linked list.

14. Blockchain (Conceptual)

• Though not implemented using traditional linked lists, blockchains follow a linked-list-like structure where each block references the previous one.

15. Circular Buffers

• Circular linked lists are used to implement buffers in real-time systems or data streams.