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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告