Linked lists

A linked list is a data structure that consists of a sequence of nodes, each of which contains a value and a reference to the next node in the sequence. Linked lists are a useful data structure when we need to store and manipulate data in a dynamic way, meaning that the size of the data may change over time. In a linked list, each node is not required to be contiguous in memory.

The first node of a linked list is called the head, and the last node is called the tail. The tail node has a reference to null, indicating the end of the list. Linked lists can be used to implement stacks, queues, and other data structures.

Here is an example of creating a linked list in JavaScript:

class Node {
 constructor(value) {
   this.value = value;
   this.next = null;
 }
}
class LinkedList {
 constructor() {
   this.head = null;
   this.tail = null;
   this.length = 0;
 }
 append(value) {
   const newNode = new Node(value);
   if (!this.head) {
     this.head = newNode;
     this.tail = newNode;
   } else {
     this.tail.next = newNode;
     this.tail = newNode;
   }
   this.length++;
 }
 prepend(value) {
   const newNode = new Node(value);
   if (!this.head) {
     this.head = newNode;
     this.tail = newNode;
   } else {
     newNode.next = this.head;
     this.head = newNode;
   }
   this.length++;
 }
 insert(index, value) {
   if (index === 0) {
     this.prepend(value);
     return;
   }
   if (index >= this.length) {
     this.append(value);
     return;
   }
   const newNode = new Node(value);
   const leader = this.traverseToIndex(index - 1);
   const temp = leader.next;
   leader.next = newNode;
   newNode.next = temp;
   this.length++;
 }
 remove(index) {
   if (index === 0) {
     this.head = this.head.next;
     this.length--;
     return;
   }
   const leader = this.traverseToIndex(index - 1);
   leader.next = leader.next.next;
   if (index === this.length - 1) {
     this.tail = leader;
   }
   this.length--;
 }
 traverseToIndex(index) {
   let currentNode = this.head;
   let counter = 0;
   while (counter !== index) {
     currentNode = currentNode.next;
     counter++;
   }
   return currentNode;
 }
}

In this example, the LinkedList class is defined with several methods, including append(), prepend(), insert(), and remove(). The append() method adds a new node to the end of the list, while the prepend() method adds a new node to the beginning of the list. The insert() method adds a new node at a specified index in the list, while the remove() method removes a node at a specified index.

The Node class represents a single node in the list and has a value property to store the value of the node and a next property to reference the next node in the list. The LinkedList class has a head property to reference the first node in the list and a tail property to reference the last node in the list. The length property keeps track of the number of nodes in the list.

The traverseToIndex() method is used internally to find the node at a specified index in the list. This method starts at the head of the list and iterates through the nodes until the specified index is reached Here are some examples of how to use the LinkedList class:

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
console.log(list); // Output: { head: Node { value: 1, next: Node { value: 2, next: Node { value: 3, next: null } } }, tail: Node { value: 3, next: null }, length: 3 }
list.prepend(0);
console.log(list); // Output: { head: Node { value: 0, next: Node { value: 1, next: Node { value: 2, next: Node { value: 3, next: null } } } }, tail: Node { value: 3, next: null }, length: 4 }
list.insert(2, 1.5);
console.log(list); // Output: { head: Node { value: 0, next: Node { value: 1, next: Node { value: 1.5, next: Node { value: 2, next: Node { value: 3, next: null } } } } }, tail: Node { value: 3, next: null }, length: 5 }
list.remove(3);
console.log(list); // Output: { head: Node { value: 0, next: Node { value: 1, next: Node { value: 1.5, next: Node { value: 3, next: null } } } }, tail: Node { value: 3, next: null }, length: 4 }

In this example, we create a new LinkedList object and add several nodes to it using the append() method. We then prepend a new node to the list using the prepend() method, insert a new node at index 2 using the insert() method, and remove a node at index 3 using the remove() method. The output shows the resulting LinkedList object after each operation.

Linked lists can be used in a variety of applications, such as implementing caches, file systems, and web browsers.