Javascript 中 LinkedList 的實現-js教程-PHP中文網

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 中新增或刪除資料。

以上是Javascript 中 LinkedList 的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！