A Deep Dive into Advanced Linked List Implementations in JavaScript
Tags: javascript, webdev, beginners, tutorial
Published: 2023-02-21 23:53:37

## 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:

```js
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.

```js
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.

```js
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.

```js
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.

```js
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.

```js
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.

```js
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.

```js
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.