>> [音樂播放]
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。