首頁 >web前端 >js教程 >帶有JavaScript的數據結構:單連鎖列表和雙關聯列表

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

Lisa Kudrow
Lisa Kudrow原創
2025-03-13 12:52:11359瀏覽

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

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

了解單連鎖的列表

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

單連接的列表操作

我們將檢查NodeSinglyList (或在我們的情況下是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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn