本文探討了單獨且雙重鏈接的列表,這是計算機科學中的兩個基本數據結構。通常會誤解這些結構,最好通過相關的類比來理解這些結構:尋寶遊戲。
了解單連鎖的列表
單連接的列表是一系列互連節點。每個節點都保存數據和一個指針,引用序列中的下一個節點。這反映了一個尋寶遊戲:每個線索(節點)包含一個消息(數據)和指令(指針),導致下一個線索。整個線索序列形成了完整的狩獵。
單連接的列表操作
我們將檢查Node
和SinglyList
(或在我們的情況下是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中文網其他相關文章!