在 JavaScript 中移除單鏈表中的元素

---

在給定的問題陳述中，我們得到一個單鏈表，我們的任務是從列表中刪除一個元素。因此，我們將在下面逐步討論此操作。

什麼是單鏈表？

單鏈表由一系列節點組成。它是一種資料結構。其中每個節點包含一個值或我們可以稱之為資料，以及指向序列中下一個節點的列表。列表中的第一個節點稱為頭部，列表中的最後一個節點指向 null，這表示列表的末尾。

下面是單鏈表的視覺化示例

在上面的示例中，連結串列包含具有兩個值的節點。第一個是資料部分，第二個是指向下一個節點的引用點。這就是序列的形成方式。

單鏈表的主要特性是它允許在列表開頭或給定節點之後高效地插入和刪除。但是訪問列表中間的專案或搜尋值具有線性時間複雜度，需要從末尾遍歷列表。

當我們需要頻繁地透過在開頭或結尾新增或刪除元素來更新或修改列表時，這些連結很有用。

理解問題

問題是給定一個連結串列，其中包含連線到每個後續值的元素。我們需要實現一個函式，該函式將從列表中刪除指定的元素。例如，我們有一個像 1 -> 2 -> 3 -> 4 -> 5 這樣的列表，這是一個連結串列，每個元素都連線到其下一個元素，我們需要刪除該元素，假設我們要從列表中刪除 4，因此刪除 4 後，連結串列將如下所示：1 -> 2 -> 3 -> 5。

給定問題的邏輯

我們給定一個單鏈表，我們必須建立一個函式，該函式從列表中刪除特定專案。為了解決此問題，我們將遍歷連結串列。並從連結串列的頭部開始。之後，我們將一次遍歷一個節點，並執行此任務，直到我們沒有找到要刪除的節點或到達列表的末尾。

然後，我們將透過檢查以下條件來刪除指定的專案：如果要刪除的專案位於列表的頭部，則將頭部更新為下一個節點。否則，在遍歷列表時，我們將跟蹤當前節點和前一個節點。如果找到要刪除的節點，則更新前一個節點的引用以跳過要刪除的節點。並返回更新後的連結串列。

演算法

步驟 1：由於我們必須從給定的連結串列中刪除專案，因此首先我們將建立一個類來表示連結串列中的節點。此類將具有兩個屬性，如“資料”，用於儲存節點的值，以及“下一個”，用於指向列表中的下一個節點。

步驟 2：建立節點後，我們將為連結串列本身建立類。它將具有一個名為 head 的屬性，該屬性將指向列表中的第一個節點。如果列表為空，則 head 將設定為 null。

步驟 3：現在，我們將定義一個方法來將專案新增到連結串列的節點中。在此，我們將使用給定的資料建立一個新節點，並將其附加到列表的末尾。每個新專案都將新增到連結串列的最後一個專案中。

步驟 4：由於我們必須執行給定的任務以從列表中刪除專案。因此，建立一個函式以從列表中刪除具有指定資料的專案。它將處理兩種情況：第一種情況是：如果要刪除的節點是頭部，則更新頭部引用以跳過當前頭部。否則，我們將遍歷列表，同時跟蹤當前節點及其前一個節點，並繼續執行此過程，直到找到要刪除的節點為止。我們將更新前一個節點的 next 引用以跳過當前節點。

步驟 5：現在我們的任務是在刪除節點後顯示連結串列。我們將從頭部開始，並將每個節點的資料追加到陣列中。最後，它將記錄連線的陣列項，用箭頭分隔。

示例

//Node in the linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// The linked list
class LinkedList {
   constructor() {
      this.head = null;
   }
   // Add items to the linked list
   add(data) {
      const newNode = new Node(data);

      if (!this.head) {
         this.head = newNode;
      } else {
         let current = this.head;
         while (current.next) {
            current = current.next;
         }
         current.next = newNode;
      }
   }
   // Remove item from the list  
   remove(data) {
      if (!this.head) {
         return;
      }

      if (this.head.data === data) {
         this.head = this.head.next;
         return;
      }

      let current = this.head;
      let previous = null;

      while (current && current.data !== data) {
         previous = current;
         current = current.next;
      }

      if (current) {
         previous.next = current.next;
      }
   }
   //Traverse and print the linked list
   display() {
      let current = this.head;
      let elements = [];

      while (current) {
         elements.push(current.data);
         current = current.next;
      }

      console.log(elements.join(" -> "));
   }
}

// Example
const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

console.log("Before removal:");
list.display();

list.remove(3);

console.log("After removal:");
list.display();

輸出

Before removal:
1 -> 2 -> 3 -> 4 -> 5
After removal:
1 -> 2 -> 4 -> 5

複雜度

從單鏈表中刪除專案的時態複雜度為 O(n)，其中 n 是列表中的節點數。在最壞情況下，此時間可能會增加，因為我們將不得不遍歷整個列表以獲取要刪除的節點。空間複雜度為 O(1)，因為我們正在就地修改列表，而沒有使用任何其他儲存。

結論

在給定的問題中，我們專注於從單鏈表中刪除特定專案。透過迭代列表並更新引用，我們可以有效地從列表中刪除所需的專案，時間複雜度為 O(n)。