帶有JavaScript的數據結構：單連鎖列表和雙關聯列表

本文探討了單獨且雙重鏈接的列表，這是計算機科學中的兩個基本數據結構。通常會誤解這些結構，最好通過相關的類比來理解這些結構：尋寶遊戲。

了解單連鎖的列表

單連接的列表是一系列互連節點。每個節點都保存數據和一個指針，引用序列中的下一個節點。這反映了一個尋寶遊戲：每個線索（節點）包含一個消息（數據）和指令（指針），導致下一個線索。整個線索序列形成了完整的狩獵。

單連接的列表操作

我們將檢查Node和SinglyList （或在我們的情況下是DoublyList ）構造函數的操作。

• 節點：一個包含數據的基本構建塊。
• doublyList：
  • _length ：跟踪節點的數量。
  • head ：指向第一個節點。
  • tail ：指向最後一個節點（與單連鎖列表的關鍵區別）。
  • add(value) ：添加一個新節點。
  • searchNodeAt(position) ：在特定索引處找到一個節點。
  • remove(position) ：刪除特定索引的節點。

雙關聯列表實現

讓我們在JavaScript中實現DoublyList 。

首先， Node構造函數：

類節點{
  構造函數（value）{
    this.data = value;
    this.previous = null; //指向上一個節點的指針
    this.next = null; //指向下一個節點的指針
  }
}

DoublyList構造函數：

 class doublyList {
  constructor（）{
    this._length = 0;
    this.head = null;
    this.tail = null;
  }
}

雙關聯列表方法

以下是add(value) ， searchNodeAt(position)和remove(position)的實現，並修改為雙向遍歷。

add(value) ：

添加（value）{
  const node = new node（value）;
  if（this._length）{
    this.tail.next = node;
    node.previous = this.tail;
    this.tail = node;
  } 別的 {
    this.head = node;
    this.tail = node;
  }
  this._length;
  返回節點;
}

searchNodeAt(position) ：（與單連接的列表版本相同）

 searchNodeat（位置）{
  // ...（實施保持不變）...
}

remove(position) ：

刪除（位置）{
  // ...（實施更為複雜，處理四種情況：無效的位置，卸下頭部，卸下尾巴，刪除中間節點。請參閱原始文章以獲取詳細的實現。）...
}

結論

本文使用了尋寶遊戲類比，對單一和雙重鏈接的列表進行了明確的解釋。提供的JavaScript代碼演示了雙關聯列表的實現，與單連鎖列表相比，突出了關鍵差異和復雜性。請記住嘗試代碼以鞏固您的理解。

以上是帶有JavaScript的數據結構：單連鎖列表和雙關聯列表的詳細內容。更多資訊請關注PHP中文網其他相關文章！