Javascript 中 LinkedList 的实现

javascriptjavascript 2023-08-28 11:02:21 721
摘要： 链表是一种由一系列元素组成的数据结构，每个元素都包含对该序列中下一个元素的引用（或“链接”）。第一个元素称为头，最后一个元素称为尾。链表与其他数据结构相比有很多优点。现在我们来看看如何使用JavaScript实现链...

Javascript 中 LinkedList 的实现

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

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

定义 Node 类和 LinkedList 类

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

Node 类表示链表中的单个节点。它有两个属性：data 和 next。 data 属性用于存储节点的实际数据，而 next 属性是对列表中下一个节点的引用。 Node 类由一个构造函数组成，该构造函数在创建新 Node 时初始化数据和 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 属性设置为链表的当前头即可。然后您可以将链表的头更新为新节点。这也称为链表头部插入，是最基本的数据添加类型。只需调用下面定义的 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 类添加方法来执行添加和删除数据以及打印等操作列表。重要的是还要考虑边缘情况并在实施中相应地处理它们。根据用例，有多种方法可以在 LinkedList 中添加或删除数据。

标签：