Javascript 实现链表

链表是一种数据结构，由一系列元素组成，每个元素都包含对序列中下一个元素的引用（或“链接”）。第一个元素称为头节点，最后一个元素称为尾节点。

链表相比其他数据结构有许多优点。现在我们来看看如何使用Javascript实现链表。

定义Node类和LinkedList类

这基本上是在Javascript中实现链表的先决条件。在这一步中，需要创建两个类，一个用于节点，一个用于链表。

Node类表示链表中的单个节点。它有两个属性，即data和next。data属性用于存储节点的实际数据，而next属性是指向列表中下一个节点的引用。Node类包含一个构造函数，在创建新节点时初始化data和next属性。

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

LinkedList类是链表本身的表示。它有一个head属性，指向链表中的第一个节点。LinkedList类还有一个构造函数，在创建新的LinkedList时初始化head属性。

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

LinkedList类还包含一个方法，允许您在同时执行其他操作（如打印列表、计算元素的数量、反转列表等）的情况下插入、删除和搜索列表中的节点。

打印链表

您可以通过遍历链表并打印每个节点的数据来打印链表的元素。

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

向链表添加节点

根据新节点应插入的位置，向链表添加数据有多种方法，如下所示：

向链表开头添加节点

要在链表开头添加节点/元素，在创建一个新节点并设置新节点的next属性为当前链表头之后，将新节点的next属性设置为当前链表头。然后可以将链表头更新为新节点。这也被称为在链表头部进行插入，是最基本的数据添加类型。可以通过调用下面定义的add函数来实现。

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;
}

在链表末尾添加节点

要在链表末尾添加节点/元素，我们需要遍历链表并找到最后一个节点。然后创建一个带有数据的新节点并将最后一个节点的next属性设置为新节点。这也被称为在链表尾部插入，是数据添加的第二种基本类型。只需调用下面定义的addToTail函数即可实现。

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;
}

在指定位置添加节点

为了在链表的特定位置添加节点/元素，您可以遍历列表以找到插入点前位置的节点，使用数据创建一个新节点，将新节点的next属性设置为当前位置的节点，将前一个节点的next属性设置为新节点。

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;
   }
}

示例（向链表添加节点）

在下面的示例中，我们实现了在开头、结尾和特定位置添加节点。

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();

输出

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

移除节点

根据需求，数据的移除也可以通过几种不同的方法来完成。

移除特定节点

要从链表中移除特定节点，我们需要遍历链表并找到要删除节点之前的节点，更新其next属性以跳过要删除的节点，并更新对下一个节点的引用。这样可以根据值来移除节点。

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;
}

在特定位置删除节点

要在链表中特定位置删除一个节点，我们需要遍历链表找到目标节点的前一个节点，更新它的next属性跳过要删除的节点，并更新对下一个节点的引用。这基本上是根据索引值删除节点。

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;
}

示例（从链表中删除节点）

在下面的示例中，我们实现了从链表中删除特定节点和特定位置节点。

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();

输出

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

List after removing node at index 2
node1
node3

结论

在JavaScript中实现链表涉及创建一个表示链表中每个节点的Node类和一个表示链表本身的LinkedList类，并在LinkedList类中添加方法来执行添加和删除数据以及打印链表等操作。在实现中，还需要考虑边缘情况并相应地处理。根据使用情况，有几种添加或删除链表数据的方式。