JavaScript - 链表

链表是数据元素的有序集合。在链表中，数据将以节点 (Node) 的形式表示。节点分为两部分:第一部分保存元素的数据，第二部分(指针)存储下一个节点的地址。链表中的元素按顺序存储。

节点 (Node): 表示链表中的每个元素。它由两部分组成:数据和下一个节点。

头节点: 指向第一个元素的引用称为头节点。

下一个节点: 这是指向链表中下一个节点的指针。

链表的类型

链表有三种类型:

• 单链表:在这种类型的链表中，列表中的每个节点仅连接到列表中的下一个节点。
• 双链表:在这种类型的链表中，列表中的每个节点都连接到下一个节点和上一个节点。节点。
• 循环链表:在这种类型的链表中，最后一个节点连接到第一个节点。

链表的实现

定义节点类和点赞列表类，这基本上是在 JavaScript 中实现链表的先决条件。在此步骤中，需要创建两个类，一个用于节点，另一个用于链表。

Node 类表示链表中的单个节点。它具有两个属性:data 和 next。data 属性用于存储节点的实际数据，而 next 属性是对列表中下一个节点的引用。Node 类包含一个构造函数，该构造函数在创建新 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 类还包含一个方法，允许你在列表中插入、删除和搜索节点，同时允许执行其他操作，例如打印列表、计数元素、反转列表等等。

插入节点

要在链表中插入节点，我们需要先创建一个新节点并将数据赋值给它。然后，我们需要检查头节点是否为空，如果为空，则将新节点赋值给头节点。如果头节点不为空，则需要遍历列表直到最后一个节点，并将新节点赋值给最后一个节点的下一个节点。

insert(data) {
   let node = new Node(data);
   if (!this.head) {
      this.head = node;
      this.tail = this.head;
   } else {
      this.tail.next = node;
      this.tail = node;
   }
   this.length++;
   return this;
}

搜索节点

如果需要在链表中搜索元素，我们可以简单地遍历链表并检查当前节点数据是否等于我们要搜索的数据。如果找到了我们要搜索的数据，就可以返回该节点。

search(data) {
   let current = this.head;
   while (current) {
      if (current.data === data) {
         return current;
      }
      current = current.next;
   }
   return null;
}

删除节点

如果我们想从链表中删除一个节点，假设您有节点 prev 和节点 current，并且您想删除节点 current。您只需将 prev 的下一个节点赋值给 current 的下一个节点，节点 current 就会被删除。

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

打印链表

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

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

代码示例

以下是 JavaScript 中链表实现的示例。

<!DOCTYPE html>
<head>
<title>Linked List</title>
</head>
<body>
<p id = "demo"></p>
<script>
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}

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

   insert(data) {
      let node = new Node(data);
      if (!this.head) {
         this.head = node;
         this.tail = this.head;
      } else {
         this.tail.next = node;
         this.tail = node;
      }
      this.length++;
      return this;
   }

   search(data) {
      let current = this.head;
      while (current) {
         if (current.data === data) {
            return current;
         }
         current = current.next;
      }
      return null;
   }

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

   print() {
      let current = this.head;
      let output = "";
      while (current) {
          output += current.data + " ";
          current = current.next;
      }
      document.getElementById("demo").innerHTML = output;
   }
}

let list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
list.print();
</script>
</body>
</html>

输出

以下是上述代码的输出。

1 2 3 4 5

在上面的例子中，我们创建了一个包含元素 1、2、3、4 和 5 的链表。我们将这些元素插入到链表中并打印了该列表。