Implementation of LinkedList in Javascript

A linked list is a data structure consisting of a sequence of elements, each element containing a reference (or "link") to the next element in the sequence ). The first element is called the head and the last element is called the tail.

Linked list has many advantages compared with other data structures. Now let's take a look at how to implement a linked list using JavaScript.

Define Node class and LinkedList class

This is basically a prerequisite for implementing linked lists in JavaScript. In this step, you need to create 2 classes, one for nodes and another for linked lists.

The Node class represents a single node in a linked list. It has two properties: data and next. The data attribute is used to store the actual data of the node, while the next attribute is a reference to the next node in the list. The Node class consists of a constructor that initializes the data and next properties when creating a new Node.

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

LinkedList class is the representation of the linked list itself. It has a head attribute that refers to the first node in the list. The LinkedList class also has a constructor that initializes the head property when creating a new LinkedList.

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

The LinkedList class also contains a method that allows you to insert, delete and search nodes in the list, while allowing other operations such as printing the list, counting elements, reversing the list, etc.

Print link list

You can print the elements of the linked list by traversing the linked list and printing the data of each node.

printAll() {
   let current = this.head;
   while (current) {
      console.log(current.data);
      current = current.next;
   }
}

Add node to linked list

There are multiple ways to add data to a linked list, depending on where the new node must be inserted, as follows -

Add node to the beginning of the linked list

To add a node/element at the beginning of the linked list, once you create the new node with the data, simply set its next property to the current head of the linked list. You can then update the head of the linked list to the new node. This is also called linked list head insertion and is the most basic type of data addition. This is done simply by calling the add function defined below.

add(data) {
   const newNode = new Node(data);
   if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
   } else {
      this.tail.next = newNode;
      this.tail = newNode;
   }
   this.length++;
   return this;
}

Add node to the end of the linked list

To add a node/element at the end of the linked list, we need to traverse the linked list and find the last node. Afterwards create a new node with the data and set the last node's next property to the new node. This is also called tail insertion of a linked list and is the second most basic type of data addition. This is done simply by calling the addToTail function defined below.

addToTail(data) {
   let newNode = new Node(data);
   if (this.head === null) {
      this.head = newNode;
      return;
   }
   let current = this.head;
   while (current.next !== null) {
      current = current.next;
   }
   current.next = newNode;
}

Add nodes at specific locations

To add a node/element at a specific position in the linked list, you can traverse the linked list to find the node at the position before the insertion point, create a new node with the data, set the next attribute of the new node to the current node at that position, and replace the previous The node's next property is set to the new node.

addAtPosition(data, position) {
   let newNode = new Node(data);
   if (position === 1) {
      newNode.next = this.head;
      this.head = newNode;
      return;
   }
   let current = this.head;
   let i = 1;
   while (i < position - 1 && current) {
      current = current.next;
      i++;
   }
   if (current) {
      newNode.next = current.next;
      current.next = newNode;
   }
}

Example (add node to linked list)

In the following example, we implement adding nodes at the beginning, end and specific positions.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   //function to add data to tail
   addToTail(data) {
      let newNode = new Node(data);
      if (this.head === null) {
         this.head = newNode;
         return;
      }
      let current = this.head;
      while (current.next !== null) {
         current = current.next;
      }
      current.next = newNode;
   }
   
   // function to insert data to linked list at a particular index
   addAtPosition(data, position) {
      let newNode = new Node(data);
      if (position === 1) {
         newNode.next = this.head;
         this.head = newNode;
         return;
      }
      let current = this.head;
      let i = 1;
      while (i < position - 1 && current) {
         current = current.next;
         i++;
      }
      if (current) {
         newNode.next = current.next;
         current.next = newNode;
      }
   }
   
   // this function is used to iterate over the entire linkedlist and print
   it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();

// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after adding nodex at position 2");
list.addAtPosition("nodex",2);
list.printAll();
console.log("List after adding nodey to tail");
list.addToTail("nodey");
list.printAll();

Output

Initial List:
node1
node2
node3
node4

List after adding nodex at position 2
node1
nodex
node2
node3
node4
List after adding nodey to tail
node1
nodex
node2
node3
node4
nodey

Delete Node

Data can also be deleted through various methods upon request.

Delete specific nodes

To delete a specific node from the linked list, we need to traverse the linked list and find the node before the node to be deleted, update its next property to skip the node to be deleted, and update the reference to the next node. This will delete the node based on the value.

remove(data) {
   if (!this.head) {
      return null;
   }
   if (this.head.data === data) {
      this.head = this.head.next;
      this.length--;
      return this;
   }
   let current = this.head;
   while (current.next) {
      if (current.next.data === data) {
         current.next = current.next.next;
         this.length--;
         return this;
      }
      current = current.next;
   }
   return null;
}

Delete nodes at specific locations

To delete a node at a specific position in the linked list, we need to traverse the linked list and find the node before the node to be deleted, update its next property to skip the node to be deleted, and then update the reference to the next node. This basically deletes nodes based on their index value.

removeAt(index) {
   if (index < 0 || index >= this.length) return null;
   if (index === 0) return this.remove();
   let current = this.head;
   for (let i = 0; i < index - 1; i++) {
      current = current.next;
   }
   current.next = current.next.next;
   this.length--;
   return this;
}

Example (removing nodes from linear list)

In the following example, we implement deletion of specific nodes and nodes at specific locations.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } 
      else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   // function to remove data from linked list
   remove(data) {
      if (!this.head) {
         return null;
      }
      if (this.head.data === data) {
         this.head = this.head.next;
         this.length--;
         return this;
      }
      let current = this.head;
      while (current.next) {
         if (current.next.data === data) {
            current.next = current.next.next;
            this.length--;
            return this;
         }
         current = current.next;
      }
      return null;
   }
   
   // function to remove from a particular index 
      removeAt(index) {
      if (index < 0 || index >= this.length) return null;
      if (index === 0) return this.remove();
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
         current = current.next;
      }
      current.next = current.next.next;
      this.length--;
      return this;
   }
   
   // this function is used to iterate over the entire linkedlist and print it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();
// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after removing node2");
list.remove("node2");
list.printAll();
console.log("List after removing node at index 2");
list.removeAt(2);
list.printAll();

Output

Initial List:
node1
node2
node3
node4
List after removing node2
node1
node3
node4

List after removing node at index 2
node1
node3

in conclusion

Implementing a linked list in JavaScript involves creating a Node class to represent each node in the list and a LinkedList class to represent the list itself, and adding methods to the LinkedList class to perform operations such as adding and removing data and printing the list. It is important to also consider edge cases and handle them accordingly in the implementation. Depending on the use case, there are multiple ways to add or remove data from a LinkedList.

The above is the detailed content of Implementation of LinkedList in Javascript. For more information, please follow other related articles on the PHP Chinese website!