數據結構與算法-鏈表

鏈表的經典應用場景就是LRU緩存淘汰算法。

緩存是一種提高數據讀取性能的技術，在硬件設計、軟件開發中都有著非常廣泛的應用，比如常見的CPU緩存、數據庫緩存、瀏覽器緩存等等。

緩存的大小有限，當緩存被用滿時，哪些數據應該被清理出去，哪些數據應該被保留？這就需要緩存淘汰策略來決定。常見的策略有三種：先進先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used）。

鏈表 V.S 數組

存儲結構

數組需要一塊連續的內存空間來存儲，對內存的要求比較高。如果我們申請一個100MB大小的數組，當內存中沒有連續的、足夠大的存儲空間時，即便內存的剩余總可用空間大于100MB，仍然會申請失敗。

而鏈表恰恰相反，它并不需要一塊連續的內存空間，它通過“指針”將一組零散的內存塊串聯起來使用，所以如果我們申請的是100MB大小的鏈表，根本不會有問題。

鏈表結構

單鏈表、雙向鏈表和循環鏈表

單鏈表

我們剛剛講到，鏈表通過指針將一組零散的內存塊串聯在一起。其中，我們把內存塊稱為鏈表的“結點”。為了將所有的結點串起來，每個鏈表的結點除了存儲數據之外，還需要記錄鏈上的下一個結點的地址。如圖所示，我們把這個記錄下個結點地址的指針叫作后繼指針next。

其中有兩個結點是比較特殊的，它們分別是第一個結點和最后一個結點。我們習慣性地把第一個結點叫作頭結點，把最后一個結點叫作尾結點。其中，頭結點用來記錄鏈表的基地址。有了它，我們就可以遍歷得到整條鏈表。而尾結點特殊的地方是：指針不是指向下一個結點，而是指向一個空地址NULL，表示這是鏈表上最后一個結點。

與數組一樣，鏈表也支持數據的查找、插入和刪除操作。

我們知道，在進行數組的插入、刪除操作時，為了保持內存數據的連續性，需要做大量的數據搬移，所以時間復雜度是O(n)。而在鏈表中插入或者刪除一個數據，我們并不需要為了保持內存的連續性而搬移結點，因為鏈表的存儲空間本身就不是連續的。所以，在鏈表中插入和刪除一個數據是非常快速的。

針對鏈表的插入和刪除操作，我們只需要考慮相鄰結點的指針改變，所以對應的時間復雜度是O(1)。

但是，有利就有弊。鏈表要想隨機訪問第k個元素，就沒有數組那么高效了。因為鏈表中的數據并非連續存儲的，所以無法像數組那樣，根據首地址和下標，通過尋址公式就能直接計算出對應的內存地址，而是需要根據指針一個結點一個結點地依次遍歷，直到找到相應的結點。

你可以把鏈表想象成一個隊伍，隊伍中的每個人都只知道自己后面的人是誰，所以當我們希望知道排在第k位的人是誰的時候，我們就需要從第一個人開始，一個一個地往下數。所以，鏈表隨機訪問的性能沒有數組好，需要O(n)的時間復雜度。

循環鏈表

特殊的單鏈表，跟單鏈表唯一的區別就在尾結點：

單鏈表的尾結點指針指向空地址，表示這就是最后的結點了

循環鏈表的尾結點指針是指向鏈表的頭結點

和單鏈表相比，循環鏈表的優點是從鏈尾到鏈頭比較方便。當要處理的數據具有環型結構特點時，就特別適合采用循環鏈表。比如約瑟夫問題。

在實際軟件開發中，更常用的鏈表結構：

雙向鏈表

單向鏈表只有一個方向，結點只有一個后繼指針next指向后面的結點。而雙向鏈表，顧名思義，它支持兩個方向，每個結點不止有一個后繼指針next指向后面的結點，還有一個前驅指針prev指向前面的結點。

雙向鏈表需要額外的兩個空間來存儲后繼結點和前驅結點的地址。所以，如果存儲同樣多的數據，雙向鏈表要比單鏈表占用更多的內存空間。雖然兩個指針比較浪費存儲空間，但可以支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性。

使用場景

從結構上來看，雙向鏈表可以支持O(1)時間復雜度的情況下找到前驅結點，正是這樣的特點，也使雙向鏈表在某些情況下的插入、刪除等操作都要比單鏈表簡單、高效。

你可能會說，我剛講到單鏈表的插入、刪除操作的時間復雜度已經是O(1)了，雙向鏈表還能再怎么高效呢？別著急，剛剛的分析比較偏理論，很多數據結構和算法書籍中都會這么講，但是這種說法實際上是不準確的，或者說是有先決條件的。我再來帶你分析一下鏈表的兩個操作。

我們先來看刪除操作。

在實際的軟件開發中，從鏈表中刪除一個數據無外乎這兩種情況：

刪除結點中“值等于某個給定值”的結點；

刪除給定指針指向的結點。

對于第一種情況，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結點，都需要從頭結點開始一個一個依次遍歷對比，直到找到值等于給定值的結點，然后再通過我前面講的指針操作將其刪除。

盡管單純的刪除操作時間復雜度是O(1)，但遍歷查找的時間是主要的耗時點，對應的時間復雜度為O(n)。根據時間復雜度分析中的加法法則，刪除值等于給定值的結點對應的鏈表操作的總時間復雜度為O(n)。

對于第二種情況，我們已經找到了要刪除的結點，但是刪除某個結點q需要知道其前驅結點，而單鏈表并不支持直接獲取前驅結點，所以，為了找到前驅結點，我們還是要從頭結點開始遍歷鏈表，直到p->next=q，說明p是q的前驅結點。

但是對于雙向鏈表來說，這種情況就比較有優勢了。因為雙向鏈表中的結點已經保存了前驅結點的指針，不需要像單鏈表那樣遍歷。所以，針對第二種情況，單鏈表刪除操作需要O(n)的時間復雜度，而雙向鏈表只需要在O(1)的時間復雜度內就搞定了！

同理，如果我們希望在鏈表的某個指定結點前面插入一個結點，雙向鏈表比單鏈表有很大的優勢。雙向鏈表可以在O(1)時間復雜度搞定，而單向鏈表需要O(n)的時間復雜度。你可以參照我剛剛講過的刪除操作自己分析一下。

除了插入、刪除操作有優勢之外，對于一個有序鏈表，雙向鏈表的按值查詢的效率也要比單鏈表高一些。因為，我們可以記錄上次查找的位置p，每次查詢時，根據要查找的值與p的大小關系，決定是往前還是往后查找，所以平均只需要查找一半的數據。

現在，你有沒有覺得雙向鏈表要比單鏈表更加高效呢？這就是為什么在實際的軟件開發中，雙向鏈表盡管比較費內存，但還是比單鏈表的應用更加廣泛的原因。如果你熟悉Java語言，你肯定用過LinkedHashMap這個容器。如果你深入研究LinkedHashMap的實現原理，就會發現其中就用到了雙向鏈表這種數據結構。

實際上，這里有一個更加重要的知識點需要你掌握，那就是用空間換時間的設計思想。當內存空間充足的時候，如果我們更加追求代碼的執行速度，我們就可以選擇空間復雜度相對較高、但時間復雜度相對很低的算法或者數據結構。相反，如果內存比較緊缺，比如代碼跑在手機或者單片機上，這個時候，就要反過來用時間換空間的設計思路。

還是開篇緩存的例子。緩存實際上就是利用了空間換時間的設計思想。如果我們把數據存儲在硬盤上，會比較節省內存，但每次查找數據都要詢問一次硬盤，會比較慢。但如果我們通過緩存技術，事先將數據加載在內存中，雖然會比較耗費內存空間，但是每次數據查詢的速度就大大提高了。

所以我總結一下，對于執行較慢的程序，可以通過消耗更多的內存（空間換時間）來進行優化；而消耗過多內存的程序，可以通過消耗更多的時間（時間換空間）來降低內存的消耗。你還能想到其他時間換空間或者空間換時間的例子嗎？

了解了循環鏈表和雙向鏈表，如果把這兩種鏈表整合在一起就是一個新的版本：雙向循環鏈表。我想不用我多講，你應該知道雙向循環鏈表長什么樣子了吧？你可以自己試著在紙上畫一畫。

鏈表VS數組性能大比拼

通過前面內容的學習，你應該已經知道，數組和鏈表是兩種截然不同的內存組織方式。正是因為內存存儲的區別，它們插入、刪除、隨機訪問操作的時間復雜度正好相反。

不過，數組和鏈表的對比，并不能局限于時間復雜度。而且，在實際的軟件開發中，不能僅僅利用復雜度分析就決定使用哪個數據結構來存儲數據。

數組簡單易用，在實現上使用的是連續的內存空間，可以借助CPU的緩存機制，預讀數組中的數據，所以訪問效率更高。而鏈表在內存中并不是連續存儲，所以對CPU緩存不友好，沒辦法有效預讀。

數組的缺點是大小固定，一經聲明就要占用整塊連續內存空間。如果聲明的數組過大，系統可能沒有足夠的連續內存空間分配給它，導致“內存不足（out of memory）”。如果聲明的數組過小，則可能出現不夠用的情況。這時只能再申請一個更大的內存空間，把原數組拷貝進去，非常費時。鏈表本身沒有大小的限制，天然地支持動態擴容，我覺得這也是它與數組最大的區別。

你可能會說，我們Java中的ArrayList容器，也可以支持動態擴容啊？我們上一節課講過，當我們往支持動態擴容的數組中插入一個數據時，如果數組中沒有空閑空間了，就會申請一個更大的空間，將數據拷貝過去，而數據拷貝的操作是非常耗時的。

我舉一個稍微極端的例子。如果我們用ArrayList存儲了了1GB大小的數據，這個時候已經沒有空閑空間了，當我們再插入數據的時候，ArrayList會申請一個1.5GB大小的存儲空間，并且把原來那1GB的數據拷貝到新申請的空間上。聽起來是不是就很耗時？

除此之外，如果你的代碼對內存的使用非常苛刻，那數組就更適合你。因為鏈表中的每個結點都需要消耗額外的存儲空間去存儲一份指向下一個結點的指針，所以內存消耗會翻倍。而且，對鏈表進行頻繁的插入、刪除操作，還會導致頻繁的內存申請和釋放，容易造成內存碎片，如果是Java語言，就有可能會導致頻繁的GC（Garbage Collection，垃圾回收）。

所以，在我們實際的開發中，針對不同類型的項目，要根據具體情況，權衡究竟是選擇數組還是鏈表。

基于鏈表實現LRU

維護一個有序單鏈表，越靠近鏈表尾部的結點是越早之前訪問的。當有一個新的數據被訪問時，我們從鏈表頭開始順序遍歷鏈表。

1.如果此數據之前已經被緩存在鏈表中了，我們遍歷得到這個數據對應的結點，并將其從原來的位置刪除，然后再插入到鏈表的頭部。

2.如果此數據沒有在緩存鏈表中，又可以分為兩種情況：

如果此時緩存未滿，則將此結點直接插入到鏈表的頭部；

如果此時緩存已滿，則鏈表尾結點刪除，將新的數據結點插入鏈表的頭部。

這樣我們就用鏈表實現了一個LRU緩存，是不是很簡單？

現在我們來看下m緩存訪問的時間復雜度是多少。因為不管緩存有沒有滿，我們都需要遍歷一遍鏈表，所以這種基于鏈表的實現思路，緩存訪問的時間復雜度為O(n)。

實際上，我們可以繼續優化這個實現思路，比如引入散列表（Hash table）來記錄每個數據的位置，將緩存訪問的時間復雜度降到O(1)。因為要涉及我們還沒有講到的數據結構，所以這個優化方案，我現在就不詳細說了，等講到散列表的時候，我會再拿出來講。

除了基于鏈表的實現思路，實際上還可以用數組來實現LRU緩存淘汰策略。如何利用數組實現LRU緩存淘汰策略呢？我把這個問題留給你思考。

總結

和數組相比，鏈表更適合插入、刪除操作頻繁的場景，查詢的時間復雜度較高。不過，在具體軟件開發中，要對數組和鏈表的各種性能進行對比，綜合來選擇使用兩者中的哪一個。

數據結構 軟件開發

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。