[音樂播放] DOUG LLOYD：好吧。 所以，如果你剛剛完成的 視頻單鍊錶遺憾 我離開你關上一 懸念位。 不過，我很高興你在這裡完成 雙鍊錶的故事。 

所以，如果你還記得 該視頻中，我們談到 有關如何單鏈接 名單做參加我們的能力 處理信息 其中的元素數 或項目中的數 清單可以擴大或縮小。 現在，我們可以處理 類似的東西，在這裡 我們不能處理它使用數組。 

但他們從一個人受 嚴格的限制這 的是，與單鏈接 列表中，我們永遠只能移動 在通過列表中的單個方向。 而唯一的真實情況 在這裡，可以成為一個問題 是當我們試圖 刪除單個元件。 而我們甚至沒有討論該怎麼辦呢 在一個單鍊錶在偽代碼。 這當然是可行的，但 它可以是一個有點麻煩。 所以，如果你發現自己 在一個情況下 你想刪除 從列表中單個元素 或者它會被要求 你會被刪除 從單要素 列表中，您可能希望 考慮使用雙聯 列出代替單鏈接列表。 由於雙鍊錶讓你 移動向前和向後 通過列表，而不是 通過列表中 - 只是前進 只需通過添加一個額外的元素 我們的結構定義 對於雙鍊錶節點。 

同樣，如果你​​不打算 被刪除單個元素 從列表中 - 因為我們增加 一個額外的領域我們的結構 定義，節點本身 對於雙鍊錶 將要大一些。 他們將採取 最多的內存多個字節。 所以，如果這是不是 你將需要做的， 你可能會決定它的 不值得的權衡 不得不花費額外的 所需的內存字節 對於一個雙向鍊錶，如果你不 要被刪除的單元素。 但他們也很酷 對於其他的一些東西。 

因此，正如我所說的，我們只需要添加 一個單一的領域到我們的結構 definition--這個概念 對以前的指針。 因此，與一個單鍊錶，我們 具有值和下一步指針， 因此，雙向鍊錶只是有 一種方式向後移動為好。 

現在，在單鏈接 名單視頻中，我們談到 關於這些是五個 你需要主要的東西 能夠做到鍊錶來工作。 對於大多數的這些，但事實上 這是一個雙向鍊錶 是不是一個真正的大跳躍。 我們仍然可以通過搜索，只需 前進，從開始到結束。 我們仍然可以創建一個節點出 空氣稀薄，幾乎以同樣的方式。 我們幾乎可以刪除列表 大致相同的方式得。 唯一的事情， 有微妙的不同， 確實，在插入 新節點進入榜單， 我們將最後說說刪除 從列表中的單個元素為好。 此外，相當多 其他三，我們 不打算談論他們 現在，因為他們只是 在思想非常小的調整討論 在單鍊錶視頻。 

因此，讓我們插入一個新節點 成雙向鍊錶。 我們談到這樣做的 單鍊錶為好， 但有一對夫婦的額外 捕獲與雙鍊錶。 我們[？在的頭上傳球？] 在這裡列出一些任意值， 而我們想要得到的新掌門人 名單出這個功能。 這就是為什麼它返回一個dllnode明星。 那麼哪些步驟？ 它們是，再次，非常相似 以單鍊錶 有一個額外的補充。 我們要分配空間用於新的 節點和檢查，以確保它是有效的。 我們要填補這個節點了 與任何信息，我們 希望把它。 過去的事情，我們需要do--的 我們需要做額外的事，rather-- 是修復上的指針 老人頭列表中。 請記住，因為 的雙鍊錶， 我們可以繼續前進 和backwards--這 意味著每個節點實際上指向 其他兩個節點，而不是只是一個。 因此，我們需要解決 老人頭列表 向後指向的新負責人 鍊錶，這是一件 我們沒有做到過。 和以前一樣，我們只返回一個 指針到列表中的新掌門人。 

所以這裡有一個列表。 我們要插入12到列表中。 注意，圖 略有不同。 每個節點包含三個fields-- 數據，和一個下一指針在紅， 和以前的指針為藍色。 沒有一樣是在15點之前， 所以以前的指針為空。 這是列表的開頭。 沒有什麼之前。 而沒有一樣是在10點之後，以及 所以它的下一個指針為空也是如此。 

因此，讓我們添加12到這個列表。 我們需要[聽不清]為節點的空間。 我們把它的12內。 再然後，我們需要的是真正的 注意不要打破鏈。 我們要重新排列的 指針以正確的順序。 有時可能mean-- 正如我們將看到特別 與delete--，我們確實有一些 多餘的三分球，不過沒關係。 

那我們首先要幹什麼？ 我會建議 你或許應該的事情 這樣做是填補了12的指針 節點之前你接觸其他人。 那麼，什麼是12將指向下一個？ 15。 什麼來12前？ 什麼也沒有。 現在我們已經填補了 在12額外的信息 因此它具有上，下，和價值。 

現在，我們可以有15--這種額外 一步，我們正在談論about--我們 可以有15點回12。 現在，我們可以將頭 該鏈接的表也為12。 所以這是非常類似於我們 在做與單鍊錶， 除了額外的步驟 連接老臉名單 返回列表的新掌門人。 

現在，讓我們終於刪除 從鍊錶中的節點。 所以我們可以說，我們有 其他一些功能 是找到我們要刪除一個節點 並給了我們一個指針準確 我們要刪除的節點。 我們甚至不need--說 頭仍然是全球範圍內宣布。 我們並不需要在這裡頭。 所有這些功能做的是我們已經 發現了一個指針完全節點我們 想擺脫的。 讓我們擺脫它。 這是一個很大，使用更加簡單 雙鍊錶。 First--它實際上 只是一對夫婦的事情。 我們只需要修復周圍 節點的指針，讓他們跳過 節點，我們想刪除。 然後我們就可以刪除該節點。 所以，再一次，我們只是經過這裡。 我們顯然已經決定， 我們要刪除的節點X. 再次，就是我 由方式 - 這裡 - 做 是一般的情況下為一個 節點是在中間。 有一對夫婦的 額外的警告，你 需要當你刪除考慮 列表的一開始 或列表的最後。 有一組特殊的 角落的情況下，處理那裡。 

因此，這適用於刪除任何節點 在列表中 - 一個中間那 有一個合法的指針向前 和一個合法的指針向後， 正當一個和下一個指針。 再次，如果你的工作 與結束，你 需要處理的 略有不同， 而且我們不打算 談論這件事情。 但你也許可以 找出什麼需要 要通過觀看這部影片剛剛做。 

因此，我們已經分離出X，X是節點 我們想從列表中刪除。 我們該怎麼辦？ 首先，我們需要重新安排 外面的指針。 我們需要重新安排 9的下一個跳過13 並指向10--這 就是我們剛才所做的事情。 而且，我們還需要 重新安排10的前 指向而不是指向13到9。 

如此反复，這是 圖開始。 這是我們的產業鏈。 我們需要跳過13， 但我們也需要維護 列表的完整性。 我們不希望失去任何 在任一方向的信息。 因此，我們需要重新安排 指針仔細 所以我們不打破鏈上的所有。 

所以我們可以說9的下一個指針 指向同一個地方 那個13的下 指針指向現在。 因為我們是最後 會想跳過13。 所以，在13點旁邊，你 希望朝九晚指向同去。 不過就是這樣。 然後只要13分回 到，無堅不摧13日之​​前， 我們希望10點 到，而不是13。 現在請注意，如果你遵循 箭頭，我們可以下降13 實際上不丟失任何信息。 我們已經把名單的完整性， 向前和向後移動兩者。 然後我們就可以只排序 對清理一點點 通過拉動名單在一起。 因此，我們重新安排了 指針在任一側。 然後我們釋放的X 節點包含13， 我們沒有打破鏈。 因此，我們做得很好。 

最後要注意這裡鍊錶。 因此，無論單電荷和雙聯 單，因為我們已經看到， 支持真正有效插入 和刪除元素。 你幾乎可以做 它在固定的時間。 我們有什麼做刪除 一個元素就在一秒鐘前？ 我們移動一個指針。 我們搬到另一個指針。 我們釋放X--了三次手術。 它總是需要三個操作 刪除node--釋放一個節點。 

我們如何插入？ 好了，我們只是一直 套結的開始 如果我們要插入效率。 因此，我們需要rearrange-- 這取決於它是否在 一個單電荷或雙聯 列表中，我們可能需要做三 或四則運算最大。 但同樣，它總是三個或四個。 不要緊，有多少 元素在我們的名單， 它總是三四operations-- 就像缺失始終是 三個或四個操作。 這是恆定的時間。 所以，這真的很棒。 

數組，我們正在做 像插入排序。 你可能還記得，插入 排序不是一個常數時間算法。 它實際上是相當昂貴的。 所以這是一個很大的插好。 但正如我所提到的 單鍊錶視頻， 我們已經有了一個缺點也在這裡，對不對？ 我們已經失去了能力， 隨機訪問元素。 我們不能說，我想元數四 或元件的一個鍊錶10號 同樣的方式，我們可以 做到這一點與數組 或者我們可以直接索引 到我們的數組中的元素。 

所以試圖找到一個 在鏈接列表中 - 元素 如果搜索important-- 現在可能需要線性時間。 由於名單很長，它 可能需要一個額外的步驟 對於列表中的每一個元件在 為了找到我們所要尋找的。 因此，有權衡。 有一點親 這裡CON元素。 

和雙鍊錶是不 最後一種數據結構組合 我們將談論， 把所有的基本構建 的C塊的放在一起。 因為事實上，我們可以 甚至做的比這更好 創建一個數據結構，它 你也許可以通過搜索 在固定的時間了。 但更多的，在另一個視頻。 

我是道格·勞埃德。 這是CS50。