[音樂播放] 

DOUG LLOYD：好，因此在 這一點在使用過程中， 我們已經介紹了很多C的基礎知識 我們知道了很多關於變量，數組， 指針，所有的好東西。 排序的所有這些都是建立 在看到的基本面， 但我們可以做更多的，對不對？ 我們可以結合東西 一起以有趣的方式。 

因此，讓我們做的是，讓我們開始 另闢蹊徑的什麼C給我們， 並開始創建自己的數據 利用這些建築結構 塊一起做一些事情 真正有價值的，有用的。 我們能做到這一點的方法之一是 談收藏。 因此，到目前為止，我們已經有某一種數據 結構較集合 對喜歡價值觀，相似的價值觀。 這將是一個數組。 我們有一個整數集合或 字符等的集合。 

的結構也進行排序數據的 結構收集信息， 但它不是用來收集類似的值。 它通常混合了不同的數據類型 一起在單一盒子。 但它本身並不是 用於鏈接在一起 或者連接到一起類似 項，如一個數組。 數組是偉大的 元素查找，但召回 這是非常困難 插入到一個數組， 除非我們插入的 該數組的末尾。 

而最好的例子，我有 因為這是插入排序。 如果你還記得我們的視頻 在插入排序， 有很多的 參與其費用 拿起元素，將它們轉移 出適合的東西的方式 成陣列的中間。 陣列也從另一個患 問題，這是不靈活。 當我們聲明一個數組， 我們這一次機會吧。 我們得到的說法，我想 這些元素。 可能是100，它可能 是1000，它可能 是x，其中x是一個數字，用戶 給了我們一個提示，或在命令 行。 

但是，我們只有一次機會吧，我們 沒有得到，然後說，哦，其實我 需要101，或者我需要X加20。 太晚了，我們已經宣布了 數組，如果我們想要獲得101或x 加上20，我們要聲明 一個完全不同的陣列， 複製數組中的所有元素 過來，然後我們有足夠。 而如果我們又錯了，是什麼 如果我們真的需要102或x加40， 我們要再次做到這一點。 因此，他們非常不靈活 對於調整我們的數據， 但如果我們結合在一起的一些 我們已經已經基本知識 了解指針和結構， 特別是使用動態存儲 分配使用malloc，我們 可以把這些碎片拼湊起來 創建一個新的數據結構 - 一個 單鍊錶，我們可能say-- 這使我們能夠成長， 收縮值的集合 我們不會有任何浪費的空間。 

所以，再一次，我們稱這樣的想法， 這個概念，一個鍊錶。 特別是，在這個視頻我們 談到單向鍊錶， 然後另一個視頻中，我們將討論 關於雙向鍊錶，這 只是在這裡一個主題的變化。 但一個單向鍊錶 由節點， 節點僅僅是一個抽象的term-- 這只是一些我打電話 這是一種 結構，基本上，我？ 只是要稱之為node--，這 節點具有兩個構件，或兩個字段。 它的數據，通常是一個 整數，字符浮子， 或者可以是某種其他數據類型 您已經定義了類型定義。 它包含一個指向 相同類型的另一節點。 

因此，我們有兩件事情裡面 這個節點，數據和指針 到另一個節點。 如果你開始顯現 這一點，你可以考慮一下 像鏈節點的那 連接在一起。 我們的第一個節點，它 包含數據，和一個指針 到第二個節點，其中包含 數據，和一個指針到該第三節點。 所以這就是為什麼我們稱它為 鏈接列表，它們鏈接在一起。 

這是什麼特別的 節點結構是什麼樣子？ 好吧，如果你從我們的視頻回憶 定義自定義類型，類型高清， 我們可以定義一個結構 - 和 鍵入這樣定義的結構。 tyepdef結構sllist，然後我 使用這個詞的價值在這裡隨意 以指示真的任何數據類型。 你可以傳遞一個整數或浮點數， 你可以有一切你想要的。 它不再僅僅限於 整數，或者類似的東西。 因此，值是任意 數據類型，然後一個指針 到同一類型的另一節點。 

現在，有一個小抓 這裡定義的結構 當它是一個自我參照結構。 我必須有一個臨時的 命名為我的結構。 在這一天我的結束 顯然想將它命名 SLL節點，這是最終的新 名字我喜歡的類型定義的一部分， 但我不能使用SLL節點 在這中間。 是的原因，我沒有 創建了一個名為類型SLL節點 直到我在這裡打這個最後一點。 直到這一點，我必須有 另一種方式來參考此數據類型。 

而這是一個自 參照數據類型。 它; S的一個數據類型 結構，它包含一個數據， 和一個指針到另一個 相同類型的結構。 所以，我需要能夠引用 這種數據類型至少暫時 所以給它一個暫時的 結構sllist名 讓我那麼說我想要一個 指向另一個結構sllist， 一個結構sllist明星，然後 我已經完成了定義後， 我現在可以把這種類型的SLL節點。 

所以這就是為什麼你看到有 一個臨時的名字在這裡， 但這裡的永久名字。 有時候，你可能會看到 結構的定義， 例如，是不 自我指涉，是 沒有說明的名字在這裡。 它只想說typedef結構， 打開大括號，然後定義它。 但是，如果你是結構是自 引用，因為這個人是， 你需要指定一個 臨時類型名稱。 但最終，現在 我們已經做到了這一點， 我們只能參考 這些節點，這些單位， 作為目的SLL節點 這段視頻的其餘部分。 

好吧，讓我們知道如何 創建一個鏈接列表節點。 我們知道如何定義 一個鏈接列表節點。 現在，如果我們要開始 用它們來收集信息， 有一對夫婦經營的我們 需要了解和使用。 我們需要知道如何創建 鍊錶憑空。 如果沒有清單已經， 我們要開始的。 因此，我們需要能夠 以創建一個鍊錶， 我們需要大概搜索 通過鏈接列表 找到我們正在尋找的元素。 我們需要的是能夠插入 新事物進入榜單， 我們希望我們的名單能夠成長。 同樣，我們希望能夠 從我們的名單中刪除的東西， 我們希望我們的名單，以便能夠收縮。 而在年底我們 計劃，特別是 如果你還記得，我們​​是 動態分配內存 以通常建這些列表， 我們要釋放所有的內存 當我們用它做的工作。 因此，我們需要能夠刪除一個 整個鍊錶在一個失敗的一舉。 因此，讓我們通過 某些操作 和我們怎樣才能使其可視化， 在偽代碼說話特別。 因此，我們要創建一個 鍊錶，所以也許我們 要定義一個函數 這個原型。 SLL節點明星，創造，而我路過 在一個參數，一些任意數據 再次鍵入某些任意數據類型的，。 但是我returning--這個功能應該 還給我一個指針，以一個單 鏈接列表節點。 同樣，我們正在努力創造 鍊錶憑空， 所以我需要一個指針 當我做了該名單。 

那麼，什麼是這裡涉及的步驟？ 好了，第一件事我 要做的是動態 分配空間用於新的節點。 同樣，我們正在創造出來的薄 空氣中，所以我們需要為它的malloc空間。 當然，馬上 我們的malloc後， 我們經常檢查，以確保我們的 pointer--我們沒有得到回空。 因為如果我們嘗試 尊重一個空指針， 我們要遭受 段錯誤，我們不希望出現這種情況。 

然後，我們要填補該領域， 我們要初始化值字段 並初始化下一字段。 然後我們想用於：最終的 函數原型indicates--我們要 的指針返回到SLL節點。 那麼是什麼讓這個樣子視覺？ 嗯，首先我們要動態地 分配空間用於新SLL節點， 所以我們malloc--這 視覺表示 節點，我們剛剛創建。 我們檢查，以確保 它不是null--在這種情況下， 畫面不會有 示，如果它為空， 我們會耗盡內存， 所以我們好去那裡。 所以，現在我們是在步驟C， 初始化節點值字段​​。 那麼，在此基礎上功能 叫我用在這裡， 貌似我想通過在6， 所以我會在值字段6。 現在，初始化下一個字段。 好了，我該怎麼辦那裡， 旁邊有個什麼吧， 這是在列表中的唯一事情。 那麼什麼是列表中，接下來的事情？ 

它不應該指向什麼，對吧。 還有沒有別的那裡，所以有什麼 我們知道，這一概念的nothing-- 指向什麼？ 它應該是，也許我們要 把一個空指針出現， 我會代表空 指針只是一個紅盒子， 我們不能再往前走。 正如我們將看到一個小以後， 我們將有最終鏈 箭頭連接 這些節點一起， 但是當你打的 紅色的框，這就是空， 我們不能再往前走， 這是該列表的末尾。 

最後，我們只是想 返回一個指向該節點。 因此，我們會打電話給它新的， 並返回新 因此它可被用 無論函數創建它。 所以我們去，我們已經創建了一個單 鍊錶節點無中生有， 現在我們有了一個可以使用的列表。 

現在，讓我們說，我們已經 有大型連鎖， 我們要找到的東西在裡面。 我們希望有一個功能是怎麼回事 返回true或false，這取決於 在該列表中是否存在某個值。 函數原型，或 聲明該函數， 可能看起來像this-- BOOL發現，和 那麼我們想傳遞的兩個參數。 

第一，是一個指針，指向 該鏈接的表的第一個元素。 這實際上是你會 總想跟踪， 實際上可能是東西， 你甚至放在一個全局變量。 一旦你創建一個列表， 你永遠，永遠 要保持的非常軌跡 列表的第一個元素。 這樣，你可以參考其他所有 只是簡單地跟著鏈條元素， 無需保持指針 完整的每一個元素。 你只需要跟踪第一 一個，如果他們都鏈接在一起。 

然後是第二件事 我們傳遞再次 是任意some-- 我們的任何數據類型 尋找有內 希望列表中的節點之一。 那麼哪些步驟？ 好了，我們做的第一件事是 我們創建了一個橫向的指針 指向列表頭部。 那麼，為什麼我們這樣做，我們已經 有一個指針在表頭， 為什麼我們不只是移動了一繞？ 嗯，就像我剛才說的， 這對我們來說真的很重要 要始終保持軌道的 列表中的第一個元素。 所以它實際上更好 創建一個副本， 並用它來從不左右移動，所以我們 意外離開，否則我們永遠 有一個指針在某些時候是 右邊上的列表中的第一個元素。 因此，它是最好創建一個 我們使用移動第二個。 

然後，我們只是比較是否 在該節點的值字段 就是我們正在尋找的東西，如果它是 不，我們只是移動到下一個節點。 我們繼續這樣做， 過來，過來，過來， 直到我們要么找到 元素，或者我們打 null--我們已經走到了盡頭 列表，它是不存在的。 這應該有希望打鈴 你剛才線性搜索， 我們只是複製它 一個單向鍊錶結構 代替使用一個陣列，以做到這一點。 

所以這裡有一個例子 一個單向鍊錶。 這其中包括 五個節點，我們有 一個指針的頭 列表中，這就是所謂的列表。 我們要做的第一件事就是 再次，創建遍歷指針。 所以，我們現在兩個指針 這點同樣的事情。 

現在，請注意這裡。此外，我也沒 必須對malloc的TRAV任何空間。 我並沒有說TRAV等於的malloc 東西時，該節點已經存在， 在內存空間已經存在。 因此，所有我實際上做的是 創建另一個指針。 我不是mallocing額外 空間，只是現在的兩個指針 指向同樣的事情。 

所以是2我在找什麼？ 哦，不，所以不是我 將移動到下一個。 所以基本上我會說， TRAV等於TRAV旁邊。 3我在尋找什麼，沒有。 所以，我繼續走 通過，直到最後 到6這就是我要找 用於基於所述函數調用 我在上面 在那裡，所以我做了。 

現在，如果元件我什麼 尋找的是不在列表中， 難道還要去上班？ 好了，注意到列表 這裡是微妙的不同， 這是另一件事是 用鍊錶重要的， 不必保留 它們在任何特定的順序。 你可以，如果你想要的，但 你可能已經注意到了 我們不是跟踪 我們是在什麼數量的元素。 

這就是那種一筆交易中，我們 有鍊錶節陣列， 難道我們沒有 隨機訪問了。 我們不能只是說，我想 去第0個元素， 或者我的數組的第6元， 我可以在一個陣列做。 我不能說我想去的 第0個元素，或者第6元， 或我的鍊錶25元件， 有沒有與之相關的索引。 因此它並不真正的問題 如果我們保留以我們的名單。 如果你想你 當然可以，但有 沒有理由，他們需要 以任何順序被保留。 如此反复，讓我們試著 在此列表中發現6。 好了，我們開始在 開始，我們沒有發現6， 然後我們繼續沒有找到 6，直到我們最終到達這裡。 所以現在TRAV指向節點 含有8，和六不在那裡。 

因此，下一步將是 去下一個指針， 所以說TRAV等於TRAV旁邊。 好了，接下來TRAV，以表示 紅色框出現，為空。 因此，有無處可 走，所以在這一點 我們可以得出結論，我們已經達到 鍊錶的末尾， 和圖6是不是在那裡。 並且將它返回 假在這種情況下。 

好了，我們怎麼插入一個新的 節點插入到鍊錶？ 因此，我們已經能夠創造 鍊錶從哪兒冒出來， 但我們可能要 建立一個鏈條，而不是 創建一批獨特的名單。 我們希望有一列表 有一堆在它的節點， 不是一堆列表與單個節點。 因此，我們不能只是一味地使用Create 功能我們前面定義的，現在我們 要插入到一個 已經存在列表。 

所以這種情況下，我們將 傳入兩個參數， 指針的頭部 鍊錶，我們要添加到。 再次，這就是為什麼它是如此 重要的是，我們始終 跟踪它，因為 這是我們唯一的辦法真的 不得不指整個列表是 剛剛通過的指針的第一個元素。 因此，我們要傳遞一個 指針，該第一元件， 和任何價值，我們 要添加到列表中。 而最終這個功能 是否會返回一個指針 到鍊錶的新掌門人。 

什麼是這裡涉及的步驟？ 好了，就像創建， 我們需要動態分配 一個新的節點空間，並進行檢查，以 確保我們不會耗盡內存，再一次， 因為我們使用的malloc。 然後，我們要填充 並插入節點， 所以放多少，什麼 val為，到節點。 我們要在插入節點 鍊錶的開頭。 

還有一個原因是我 要做到這一點，它 可能是值得考慮第二 在這裡暫停視頻， 想想我為什麼會想 在插入一個鏈接開始 名單。 再次，我前面提到的 它並沒有真正 的問題，如果我們在任何保護它 順序，所以也許這是一個線索。 而你看到的，如果我們會發生什麼 想用於：或者只是第二 以前，當我們打算 通過搜索你 可以看到什麼可能 發生，如果我們試圖 插入在列表的末尾。 因為我們沒有一個 指針的列表的末尾。 

因此原因，我想 插入開頭， 是因為我可以馬上做到這一點。 我有一個指針指向開始， 我們將看到這一場視覺在第二。 但是，如果我想插入底， 我要從頭開始， 遍歷所有的方式向 到底，然後把它釘住。 因此，這將意味著 在列表的末尾插入 將成為n的Ø 操作時，要回 我們的討論 計算複雜性。 它會變成n操作，其中的鄰 作為列表越來越大，大， 大，它會變得越來越 更難以粘性的東西 上在末端。 但它總是很容易 釘東西之初， 你總是在開頭。 

我們將看到一個可視化的這個了。 然後，一旦我們完成了，一旦 我們插入新的節點， 我們希望我們的指針返回 鍊錶新的頭，這 因為我們要插入在 開始，居然會 一個指向我們剛剛創建的節點。 讓我們想像這一點， 因為我認為這將幫助。 

因此，這裡是我們的名單，它由 四個元素，一個節點含有15， 它指向一個節點 含有9，其 指向包含13的節點， 指向包含一個節點 10，它具有空 指針作為其下一個指針 所以這是該列表的末尾。 因此，我們要插入一個 用價值12新節點 在這個初 列表中，我們怎麼辦？ 嗯，首先，我們的malloc空間的 節點，然後我們把12在那裡。 

所以，現在我們已經到了一個 決策點，對不對？ 我們有幾個 指針，我們可以 移動，哪一個應該我們搬進去？ 我們應該做出12點 列表中 - 新掌門 或不好意思，我們應該讓12 指向老首長的名單？ 或者我們應該說， 列表現在開始在12。 有一個區別 在那裡，我們將看看 在與兩國在第二會發生什麼。 

但是這將導致一個 對於側邊欄很大的話題， 這是一個的 用鍊錶最棘手的事情 被安排指針 以正確的順序。 如果你搬東西壞了， 你可以結束了意外 孤兒列表的其餘部分。 這裡是一個很好的例子。 所以，讓我們的想法of-- 好了，我們已經創建了12。 我們知道，12將是 列表中的新掌門人， 所以我們為什麼不正義之舉 該列表指針指向那裡。 

好了，這是很好的。 所以，現在在那裡做12下一個點？ 我的意思是，在視覺上我們可以看到 它將指向15， 作為人類，它真的很明顯給我們。 計算機如何知道的？ 我們沒有任何東西 指著15了，對不對？ 

我們已經失去了任何參考15的能力。 我們不能說新的箭頭旁邊的equals 什麼東西，有什麼也沒有。 事實上，我們已經成為孤兒 列表的其餘 通過這樣做，我們已經 不小心打破了鏈條。 我們當然不希望這樣做。 

因此，讓我們回去再試試這個。 也許做正確的事 是設置12的下一個指針 到舊頭部列表的第一， 那麼我們可以將名單上。 而事實上，是這樣的 正確的順序我們 需要遵循當我們 正與單向鍊錶。 我們總是希望連接 新元素到列表中， 之前，我們需要的那種 改變的重要一步 其中鍊錶的頭。 再次，這是這樣一個根本的東西， 我們不想失去它的軌道。 

所以我們要確保 一切都鏈接在一起， 我們繼續之前的指針。 所以，這將是正確的順序， 這是連接12到列表中， 然後說，該清單啟動12。 如果我們所說的名單開始在12和 然後試圖連接12到列表中， 我們已經看到發生了什麼。 我們失去了對列表進行的錯誤。 

好了，還有一件事談。 如果我們要擺脫什麼 整個鍊錶一次？ 同樣，我們mallocing 這一切的空間，所以我們 需要釋放它的時候，我們就大功告成了。 所以，現在我們想刪除 整個鍊錶。 那麼，我們要怎麼辦？ 

如果我們已經達到了空指針，我們 想停下來，否則，只是刪除 該列表的其餘部分，然後讓我自由。 刪除列表的其餘部分， 然後釋放當前節點。 這是什麼聲音一樣， 有什麼技術，我們聊 有關以前這聽起來像不像？ 刪除其他人，然後 回來並刪除了我。 

這是遞歸的，我們所做的 問題稍微小了一點， 我們說每個人都刪除 否則的話，你可以刪除我。 而進一步下跌的道路，節點 會說，否則刪除每一個人。 但最終，我們會得到的 點的列表為空， 這就是我們的基本情況。 

因此，讓我們來看看這個， 以及這可能會奏效。 因此，這裡是我們的名單，這是相同的 列出我們只是在談論， 這裡面的步驟。 有大量的文字在這裡，但 希望可視化將幫助。 

因此，我們have--，我還拉 我們的堆棧幀圖 從我們的視頻調用棧， 並希望這一切 同時會告訴你這是怎麼回事。 因此，這裡是我們的偽代碼。 如果我們到達空 指針，停止，否則， 刪除列表的其餘部分， 然後釋放當前節點。 所以，現在，列表中 -  我們是指針 傳遞摧毀點至12。 12不是一個空指針，所以我們 要刪除列表的其餘部分。 

什麼是刪除 我們剩下的參與？ 嗯，這意味著製作 呼籲摧毀，說 即圖15是的開頭 其餘的，我們要摧毀名單。 這樣一來，呼籲銷毀 12是種擱置。 它凍結在那裡，等待 呼籲摧毀15，完成其工作。 

好了，15不是一個空指針， 所以它會說，沒事， 同時，刪除列表的其餘部分。 列表的其餘部分開始 9，所以我們只 等到你刪除所有 的東西，然後回來，並刪除了我。 那麼9會說，好吧， 我不是一個空指針， 所以從這裡刪除其餘的名單。 所以盡量和銷毀13。 13說，我不是空指針， 同樣的事情，它通過降壓。 10不是空指針，10 包含一個空指針， 但10本身不是一個 空指針現在， 因此它通過降壓太。 

現在列出點那裡， 真正將指向some-- 如果我的形象有更多的空間， 它會指向一些隨機的空間 我們不知道它是什麼。 這是空指針雖然名單 簡直是現在設置它的值空。 它指向正確的紅色方框內。 我們達到了一個空指針，所以 我們可以停下來，我們就大功告成了。 

所以那紫色幀now--在 stack--的頂部是這樣的活動框架， 但它的完成。 如果我們已經達到了一個空指針，停止。 我們沒有做任何事情，我們 無法釋放空指針， 我們沒有任何的malloc 空間，所以我們就大功告成了。 這樣功能框架 被破壞，並且我們 resume--我們拿起我們離開 關具有下一最高一個，這 這是深藍色的框在這裡。 於是我們拿起身在何方，我們不放過。 我們刪除的休息 列表了，所以現在我們 要釋放當前節點。 所以，現在我們可以免費這個節點，現在 我們已經達到了函數的結束。 而這樣的功能框架被破壞， 我們拿起在淺藍色的。 

因此，says--我已經done-- 刪除列表的其餘部分，所以 釋放當前節點。 而現在的黃色框為 回堆棧的頂部。 所以你看，我們現在是 從右破壞列表中離開了。 

會發生什麼，不過， 如果我們做事情的方法不對？ 就像當我們試圖 添加元素。 如果我們搞砸鏈，如果 我們沒有連接的指針 以正確的順序，如果我們 剛剛釋放的第一個元素， 如果我們只是釋放了 頭列表，現在我們 沒有辦法參考 列表的其餘部分。 因此，我們將有 孤立的一切， 我們將不得不什麼 所謂的內存洩漏。 如果您從我們的視頻回憶 動態內存分配， 這不是很好的事情。 

因此，正如我所說， 有幾個操作 我們需要用工作 與有效鍊錶。 你可能已經注意到我省略之一， 從鏈接中刪除一個單個元件 名單。 我這樣做的原因 是它是一種實際 棘手思考如何刪除 從一個單獨的單個元件 鍊錶。 我們需要能夠跳過 一些在列表中，這 意味著我們得到一個point--我們 要刪除這node-- 但為了使其所以我們 不會丟失任何信息， 我們需要連接這 節點在這裡，在這裡。 

所以我大概那個做錯了 從視覺角度。 因此，我們在一開始，我們 列表中，我們正在著手通過， 我們要刪除此節點。 如果我們只是將其刪除， 我們已經打破了鏈條。 這個節點就在這裡 指的是一切， 它包含從這裡掉了鍊子。 

因此，我們需要做的其實 之後，我們到了這一點， 是我們需要退一步之一， 在連接這個節點，這個節點， 所以我們可以再刪除 一個在中間。 但單鍊錶不 為我們提供了一種倒退。 因此，我們需要可以保持 兩個指針，然後將它們移動 一前一後的排序斷步驟， 另外，因為我們去，或者到一個地步 然後通過發送另一個指針。 正如你所看到的， 可以變得有些混亂。 幸運的是，我們有 另一種方式來解決， 當我們談論雙向鍊錶。 

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