如何在 JavaScript 中實作單向鍊錶

嗨？ ，歡迎回到連結清單的這個系列。在上一篇文章中，我們了解了鍊錶的基礎知識，包括它們的定義、術語、與陣列的差異以及鍊錶的類型。我承諾我們會更深入地研究鍊錶的實現，所以讓我們開始吧。

課程大綱

1. 簡介
2. 實現單鍊錶
   • 建立新節點
   • 插入開頭
   • 插入末尾
   • 刪除節點
   • 搜尋節點
   • 遍歷列表
3. 結論

---

---

介紹

正如我們在上一篇文章中了解到的，連結列表是程式設計世界中的基本資料結構。它們由節點組成，其中每個節點包含資料和對序列中下一個節點（在單鍊錶中）或下一個和前一個節點（在雙向鍊錶中）的引用（或連結）。與陣列不同，鍊錶不會將元素儲存在連續的記憶體位置，從而允許高效的插入和刪除。

理解鍊錶的概念對於掌握資料結構和演算法至關重要。在本文中，我們將從單鍊錶的基礎知識開始，深入探討鍊錶的實作。

實現單鍊錶

單鍊錶是最簡單的鍊錶類型，其中每個節點都指向序列中的下一個節點。就像下圖一樣。

現在，是時候開始實現我們的單鍊錶基本操作了。我們可以嗎？

建立新節點

讓我們從建立一個新的 Node 類別開始。 Node 類別將有一個建構函數，用於接收節點的資料和一個初始設定為 null 的下一個指標。

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

這個新建立的 Node 類別（代表鍊錶中的一個節點）可以如下圖所示。

在繼續之前，讓我們建立一個 SinglyLinkedList 類別的新實例來保存我們的鍊錶操作。

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

在開頭插入

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

說明：插入到開頭就像新人插在最前面一樣。他們成為新的第一人稱，連結到之前的第一人稱。

在末尾插入

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

說明：在最後插入就像有人在最後加入隊伍一樣。我們需要走到最後找到最後一個人，然後將他們連結到新的人。

刪除節點

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

說明：刪除一個節點就像隊伍中間的某個人決定離開。我們找到那個人並將他們之前的人與他們之後的人聯繫起來。

搜尋節點

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

解釋： 搜尋節點就像嘗試在隊列中尋找特定的人。我們從前面開始詢問每個人，直到找到他們或到達終點。

遍歷列表

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

說明：穿越就像沿著隊伍走並問候每個人。我們從前面開始，一直前進，直到到達終點。

結論

在本文中，我們了解了鍊錶的基本操作以及如何在 JavaScript 中實現它們。在下一篇文章中，我們將學習雙向鍊錶。

記住，掌握鍊錶需要練習。繼續解決問題並在各種場景中實現這些資料結構。

---

---

保持更新和聯繫

確保您不會錯過本系列的任何部分，並與我聯繫以更深入地討論軟體開發（Web、伺服器、移動或抓取/自動化）、資料結構和演算法以及其他令人興奮的技術主題，請追蹤我：

• GitHub
• 領英
• X（推特）

敬請期待並祝您編碼愉快??‍??

以上是如何在 JavaScript 中實作單向鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！