A Deep Dive into Advanced Linked List Implementations in JavaScript

Introduction

LinkedLists are a common data structure used in computer science. They are made up of one or more nodes, which consist of a data element and an address that references the next node in the list. The last node in the list contains a null reference to indicate the end of the list.

In this article, we implement a LinkedList in JavaScript using two classes, Node and LinkedList. The Node class is used to create a new node in the list, while the LinkedList class manages the list as a whole.

Let's implement it based on this template:

function Node(data) {
    // Implementation
}

function LinkedList() {
  // Implementation
}

Implementation

The Node constructor takes a single argument, data, which is the value to be stored in the node. The constructor also initializes the next property to null, which will be set to the next node in the list if one exists.

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

The LinkedList constructor initializes three properties: head, tail, and length. head and tail are both initialized to null, indicating an empty list.

function LinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

The add method adds a new node to the end of the list by creating a new Node object and updating the tail property to point to the new node.

LinkedList.prototype.add = function(item) {
  const node = new Node(item);

  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    this.tail = node;
  }
  this.length++;
}

The toString method creates a string representation of the list by iterating through each node and concatenating its value to the result string.

LinkedList.prototype.toString = function() {
  let current = this.head;
  let result = "";

  while(current) {
    result += current.data.toString() + ' ';
    current = current.next;
  }

  return result.trim();
}

The getByIndex method retrieves the value of the node at a given index by iterating through the list and stopping at the node with the corresponding index.

LinkedList.prototype.getByIndex = function(index) {
  if(index > this.length - 1) {
    throw Error('List index out of bounds');
  }

  let result = this.head;
  for(let i = 0; i < index; i++) {
    result = result.next;
  }
  return result.data;
}

The remove method removes a node from the list by iterating through the list and updating the next property of the previous node to point to the next node in the list.

LinkedList.prototype.remove = function(data) {
  let current = this.head;
  if(!current) {
    return false;
  }

  if(current.data === data) {
    this.head = current.next;
    this.length--;
    return true;
  }

  while(current.next) {
    if(current.next.data === data) {
      current.next = current.next.next;
      this.length--;
      return true;
    }
    current = current.next;
  }
  return false;
}

Finally, we implement the insertAfter method, which inserts a new node into the list after a given node. This method finds the node with the given value and updates its next property to point to the new node, while the next property of the new node is set to the next property of the original node.

LinkedList.prototype.insertAfter = function(afterData, data) {
  const node = new Node(data);
  let current = this.head;

  while(current) {
    if(current.data === afterData) {
      node.next = current.next;
      current.next = node;
      this.length++;
      return true;
    }
    current = current.next;
  }

  return false;
}

Summary

In conclusion, linked lists are a fundamental data structure in computer science, and this implementation in JavaScript can serve as a useful tool for managing data in web applications. By understanding the principles behind linked lists and implementing them in code, developers can gain a deeper understanding of data structures and algorithms.