JavaScript 中的链表表示

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


链表中的操作

链表中有多种操作，包括添加节点、删除节点和搜索节点。这些操作将在以下场景中详细介绍。

创建节点

让我们看看下面链表节点的场景：

//Creating a node
class Node {
   constructor(element){
      this.element = element,
      this.next = null // next of the node will be NULL.
   }
}

在上述场景中，我们创建了一个具有两个属性的节点：element 和 next。Element 保存节点的数据，第二个属性“next”将保存指向下一个节点的指针。在上面的示例中，next 指向 NULL，因为链表中只有一个节点。

创建链表类

以下是创建链表类的方法：

class LinkedList{
   //Creates a linkedlist with passed element.
   constructor(element){
      //Creating HeadNode of Linkedlist
      this.head_of_LL = {
         element: element,
         next : null
      };
      //Length of Linkedlist is 1
      this.length = 1;
   }
}

在上面的代码片段中，我们创建了一个链表类，它将执行添加、删除和搜索节点的操作。并且此列表的长度定义为 1，因为链表中只有一个节点（head 也是最后一个节点）。

在开头添加节点

以下是向链表头部添加节点的算法：

  • 通过创建节点类的实例来创建一个新节点。
  • 将新节点的 next 指向头部。
  • 现在，将新节点设置为头部。

以下是向头部添加节点的方法：

//ADDING node at head position in Linkedlist
Add_node(element){
   
   //Creating New node
   const newNode = new Node(element);
 
   //Points this node's next to the head of next node
   newNode.next = this.head_of_LL;
 
   //Make this node as Head node
   this.head_of_LL = newNode;
 
   //Increase the length
   this.length++;
   return this;
 }

删除开头处的节点

以下是删除链表头部节点的算法：

  • 将删除元素的下一个元素设为头部。
  • 现在，将链表的长度减少 1。

以下是删除头部位置节点的方法：

delete_head_node(){
   //Next node of head will become new headnode
   this.head_of_LL = this.head_of_LL.next;
 
   //removing the node
   this.length--;
}

在这里，我们执行删除链表头部位置的元素的操作。删除元素的下一个节点将成为新的头部，并且链表的长度将减少 1。

搜索元素

以下是搜索链表中元素的算法：

遍历整个链表。

  • 现在，比较值
  • 如果找到，则返回 true
  • 否则，返回 false。

以下场景是在链表中搜索元素：

search_Node(element){
   let curr_Node = this.head_of_LL;
   //TRAVERSE the list and compare the values
   
   while(curr_Node !== null){
      if(curr_Node.element === element)
      //returns true if value is present
      return true;
      curr_Node = curr_Node.next;
   }
   // returns false if not found
   return false;
 }

链表的实现

我们正在 JavaScript 中实现链表数据结构。在链表中，我们可以执行添加和删除元素、搜索元素等操作。在下面的代码中，我们实现了所有上述操作。

示例

让我们看看下面代码的最终执行结果：

<!DOCTYPE html>
<html>
   <title>implementation of linked_list in JavaScript</title>
   <head>
      <script>
         class Node {
            constructor(element) {
               this.element = element,
               this.next = null
            }
         }
         class LinkedList {
            //Creates a linkedlist with passed element.
            constructor(element) {
               this.head_of_LL = {
                  element: element, next: null
               };
               this.length = 1;
            }
            // ADDING A NODE
            Add_node(element) {
               const newNode = new Node(element);
               newNode.next = this.head_of_LL;
               this.head_of_LL = newNode;
               this.length++;
               return this;
            }
            // DELETING A NODE
            delete_head_node() {
               this.head_of_LL = this.head_of_LL.next;
               this.length--;
            }
            //SEARCHING A NODE
            search_Node(element) {
               let curr_Node = this.head_of_LL;
               while (curr_Node !== null) {
                  if (curr_Node.element === element)
                  return true;
                  curr_Node = curr_Node.next;
               }
               return false;
            }
            getLinkedlist() {
               let getArrayList = [];
               let curr_Node = this.head_of_LL;
               while (curr_Node !== null) {
                  getArrayList.push(curr_Node.element);
                  curr_Node = curr_Node.next;
               }
               return getArrayList.join(' → ');
            }
         }
         document.write("Creating a LL with node 44:");
         document.write("<br>");
         const myLinkedList = new LinkedList(44);
         document.write(myLinkedList.getLinkedlist());
         document.write("<br>");
       
         //Adding
         document.write('Adding nodes (33, 22 and 11) at head position :');
         myLinkedList.Add_node(11);
         myLinkedList.Add_node(22);
         myLinkedList.Add_node(33);
         document.write("<br>");
         document.write(myLinkedList.getLinkedlist());
         document.write("<br>");
       
         //Deleting
         document.write('Deleting (32) node at head position :');
         myLinkedList.delete_head_node();
         document.write("<br>");
         document.write(myLinkedList.getLinkedlist());
         document.write("<br>");
       
         //Searching
         document.write('Searching for element 11 :');
         document.write("<br>");
         document.write(myLinkedList.getLinkedlist());
         document.write("<br>");
         document.write(myLinkedList.search_Node(11));
         document.write("<br>");
         document.write('Searching for element 55 :');
         document.write("<br>");
         document.write(myLinkedList.getLinkedlist());
         document.write("<br>");
         document.write(myLinkedList.search_Node(55));
      </script>
   </head>
</html>

输出

上述脚本的输出将为：

Creating a LL with node 44:
44
Adding nodes (33, 22 and 11) at head position :
33 → 22 → 11 → 44
Deleting (32) node at head position :
22 → 11 → 44
Searching for element 11 :
22 → 11 → 44
true
Searching for element 55 :
22 → 11 → 44
false

更新于: 2022-11-18

219 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告