文章目錄

• • 分類
  • 1.1 單向鏈表
  • 1.2 循環(huán)鏈表
  • 1.3 雙向鏈表
  • 鏈表VS數(shù)組
  • 如何基于鏈表實(shí)現(xiàn) LRU 緩存淘汰算法？
  • 手寫(xiě)鏈表的注意事項(xiàng)

鏈表和數(shù)組一樣，是非常常用和基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，都屬于線性表結(jié)構(gòu)。

? ? ? ?數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)，對(duì)內(nèi)存的要求比較高。如果我們申請(qǐng)一個(gè) 100MB 大小的數(shù)組，當(dāng)內(nèi)存中沒(méi)有連續(xù)的、足夠大的存儲(chǔ)空間時(shí)，即便內(nèi)存的剩余總可用空間大于 100MB，仍然會(huì)申請(qǐng)失敗。
? ? ? ?而鏈表恰恰相反，它并不需要一塊連續(xù)的內(nèi)存空間，它通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用，所以如果我們申請(qǐng)的是 100MB 大小的鏈表，根本不會(huì)有問(wèn)題。

分類

1.1 單向鏈表

? ? ? ?鏈表通過(guò)指針將一組零散的內(nèi)存塊串聯(lián)在一起。其中，我們把內(nèi)存塊稱為鏈表的“結(jié)點(diǎn)”。為了將所有的結(jié)點(diǎn)串起來(lái)，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)的地址。如圖所示，我們把這個(gè)記錄下個(gè)結(jié)點(diǎn)地址的指針叫作后繼指針 next。

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

? ? ? ?鏈表的插入和刪除是非常快的。在進(jìn)行數(shù)組的插入、刪除操作時(shí)，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，需要做大量的數(shù)據(jù)搬移，所以時(shí)間復(fù)雜度是 O(n)。而在鏈表中插入或者刪除一個(gè)數(shù)據(jù)，我們并不需要為了保持內(nèi)存的連續(xù)性而搬移結(jié)點(diǎn)，因?yàn)殒湵淼拇鎯?chǔ)空間本身就不是連續(xù)的。所以，在鏈表中插入和刪除一個(gè)數(shù)據(jù)是非常快速的，時(shí)間復(fù)雜度是O(1)（這里指的是單純的插入和刪除操作，如果插入和刪除之前需要查找肯定就不是了）。

? ? ? ?鏈表要想隨機(jī)訪問(wèn)第 k 個(gè)元素，就沒(méi)有數(shù)組那么高效了。因?yàn)殒湵碇械臄?shù)據(jù)并非連續(xù)存儲(chǔ)的，所以無(wú)法像數(shù)組那樣，根據(jù)首地址和下標(biāo)，通過(guò)尋址公式就能直接計(jì)算出對(duì)應(yīng)的內(nèi)存地址，而是需要根據(jù)指針一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)地依次遍歷，直到找到相應(yīng)的結(jié)點(diǎn)。時(shí)間復(fù)雜度是O(n) 。

1.2 循環(huán)鏈表

? ? ? ?循環(huán)鏈表跟單鏈表唯一的區(qū)別就在尾結(jié)點(diǎn)。我們知道，單鏈表的尾結(jié)點(diǎn)指針指向空地址，表示這就是最后的結(jié)點(diǎn)了。而循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)。
? ? ? ?和單鏈表相比，循環(huán)鏈表的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便。當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點(diǎn)時(shí)，就特別適合采用循環(huán)鏈表。比如著名的約瑟夫問(wèn)題。

1.3 雙向鏈表

? ? ? ?實(shí)際開(kāi)發(fā)應(yīng)用中最多的還是雙向鏈表，它支持兩個(gè)方向，每個(gè)結(jié)點(diǎn)不止有一個(gè)后繼指針 next 指向后面的結(jié)點(diǎn)，還有一個(gè)前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)。

? ? ? ? 雙向鏈表需要額外的兩個(gè)空間來(lái)存儲(chǔ)后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的地址。所以如果存儲(chǔ)同樣多的數(shù)據(jù)，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。雖然兩個(gè)指針比較浪費(fèi)存儲(chǔ)空間，但可以支持雙向遍歷，這樣也帶來(lái)了雙向鏈表操作的靈活性。

? ? ? ? 從結(jié)構(gòu)上來(lái)看，雙向鏈表可以支持 O(1) 時(shí)間復(fù)雜度的情況下找到前驅(qū)結(jié)點(diǎn)，正是這樣的特點(diǎn)，也使雙向鏈表在某些情況下的插入、刪除等操作都要比單鏈表簡(jiǎn)單、高效。為什么這么說(shuō)呢？
在實(shí)際的軟件開(kāi)發(fā)中，從鏈表中刪除一個(gè)數(shù)據(jù)無(wú)外乎這兩種情況：

• 刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)；
• 刪除給定指針指向的結(jié)點(diǎn)。

? ? ? ? 對(duì)于第一種情況，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點(diǎn)，都需要從頭結(jié)點(diǎn)開(kāi)始一個(gè)一個(gè)依次遍歷對(duì)比，直到找到值等于給定值的結(jié)點(diǎn)，然后再通過(guò)我前面講的指針操作將其刪除。盡管單純的刪除操作時(shí)間復(fù)雜度是 O(1)，但遍歷查找的時(shí)間是主要的耗時(shí)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為 O(n)。刪除值等于給定值的結(jié)點(diǎn)對(duì)應(yīng)的鏈表操作的總時(shí)間復(fù)雜度為 O(n)。
? ? ? ? 對(duì)于第二種情況，我們已經(jīng)找到了要?jiǎng)h除的結(jié)點(diǎn)，但是刪除某個(gè)結(jié)點(diǎn) q 需要知道其前驅(qū)結(jié)點(diǎn)，而單鏈表并不支持直接獲取前驅(qū)結(jié)點(diǎn)，所以，為了找到前驅(qū)結(jié)點(diǎn)，我們還是要從頭結(jié)點(diǎn)開(kāi)始遍歷鏈表，直到 p->next=q，說(shuō)明 p 是 q 的前驅(qū)結(jié)點(diǎn)。但是對(duì)于雙向鏈表來(lái)說(shuō)，這種情況就比較有優(yōu)勢(shì)了。因?yàn)殡p向鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針，不需要像單鏈表那樣遍歷。所以，針對(duì)第二種情況，單鏈表刪除操作需要 O(n) 的時(shí)間復(fù)雜度，而雙向鏈表只需要在 O(1) 的時(shí)間復(fù)雜度內(nèi)就搞定了。

? ? ? ?對(duì)于一個(gè)有序鏈表，雙向鏈表的按值查詢的效率也要比單鏈表高一些。因?yàn)?#xff0c;我們可以記錄上次查找的位置 p，每次查詢時(shí)，根據(jù)要查找的值與 p 的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。

? ? ? ?現(xiàn)在，你有沒(méi)有覺(jué)得雙向鏈表要比單鏈表更加高效呢？這就是為什么在實(shí)際的軟件開(kāi)發(fā)中，雙向鏈表盡管比較費(fèi)內(nèi)存，但還是比單鏈表的應(yīng)用更加廣泛的原因。Java 語(yǔ)言中的LinkedList和LinkedHashMap 容器實(shí)現(xiàn)原理就用到了雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)。
? ? ? ?實(shí)際上，這里有一個(gè)空間換時(shí)間的設(shè)計(jì)思想。當(dāng)內(nèi)存空間充足的時(shí)候，如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對(duì)較高、但時(shí)間復(fù)雜度相對(duì)很低的算法或者數(shù)據(jù)結(jié)構(gòu)。相反，如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上，這個(gè)時(shí)候，就要反過(guò)來(lái)用時(shí)間換空間的設(shè)計(jì)思路。還是開(kāi)篇緩存的例子。緩存實(shí)際上就是利用了空間換時(shí)間的設(shè)計(jì)思想。如果我們把數(shù)據(jù)存儲(chǔ)在硬盤(pán)上，會(huì)比較節(jié)省內(nèi)存，但每次查找數(shù)據(jù)都要詢問(wèn)一次硬盤(pán)，會(huì)比較慢。但如果我們通過(guò)緩存技術(shù)，事先將數(shù)據(jù)加載在內(nèi)存中，雖然會(huì)比較耗費(fèi)內(nèi)存空間，但是每次數(shù)據(jù)查詢的速度就大大提高了。

鏈表VS數(shù)組

數(shù)組和鏈表是兩種截然不同的內(nèi)存組織方式。正是因?yàn)閮?nèi)存存儲(chǔ)的區(qū)別，它們插入、刪除、隨機(jī)訪問(wèn)操作的時(shí)間復(fù)雜度正好相反。
? ? ? ?數(shù)組簡(jiǎn)單易用，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助 CPU 的緩存機(jī)制，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問(wèn)效率更高。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以對(duì) CPU 緩存不友好，沒(méi)辦法有效預(yù)讀。
? ? ? ?數(shù)組的缺點(diǎn)是大小固定，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間。如果聲明的數(shù)組過(guò)大，系統(tǒng)可能沒(méi)有足夠的連續(xù)內(nèi)存空間分配給它，導(dǎo)致“內(nèi)存不足（out of memory）”。如果聲明的數(shù)組過(guò)小，則可能出現(xiàn)不夠用的情況。這時(shí)只能再申請(qǐng)一個(gè)更大的內(nèi)存空間，把原數(shù)組拷貝進(jìn)去，非常費(fèi)時(shí)。
? ? ? ? 鏈表本身沒(méi)有大小的限制，天然地支持動(dòng)態(tài)擴(kuò)容，我覺(jué)得這也是它與數(shù)組最大的區(qū)別。
? ? ? ? 如果你的代碼對(duì)內(nèi)存的使用非常苛刻，那數(shù)組就更適合你。因?yàn)殒湵碇械拿總€(gè)結(jié)點(diǎn)都需要消耗額外的存儲(chǔ)空間去存儲(chǔ)一份指向下一個(gè)結(jié)點(diǎn)的指針，所以內(nèi)存消耗會(huì)翻倍。而且對(duì)鏈表進(jìn)行頻繁的插入、刪除操作，還會(huì)導(dǎo)致頻繁的內(nèi)存申請(qǐng)和釋放，容易造成內(nèi)存碎片，就有可能會(huì)導(dǎo)致頻繁的 GC（Garbage Collection，垃圾回收）。
? ? ? ? 和數(shù)組相比，鏈表更適合插入、刪除操作頻繁的場(chǎng)景，查詢的時(shí)間復(fù)雜度較高。在具體軟件開(kāi)發(fā)中，要對(duì)數(shù)組和鏈表的各種性能進(jìn)行對(duì)比，綜合來(lái)選擇使用兩者中的哪一個(gè)。

如何基于鏈表實(shí)現(xiàn) LRU 緩存淘汰算法？

? ? ? ? 緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，比如常見(jiàn)的 CPU 緩存、數(shù)據(jù)庫(kù)緩存、瀏覽器緩存等等。緩存的大小有限，當(dāng)緩存被用滿時(shí)，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來(lái)決定。常見(jiàn)的策略有三種：先進(jìn)先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

如何基于鏈表實(shí)現(xiàn) LRU 緩存淘汰算法？
? ? ? ? 我們維護(hù)一個(gè)有序單鏈表，越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪問(wèn)的。當(dāng)有一個(gè)新的數(shù)據(jù)被訪問(wèn)時(shí)，我們從鏈表頭開(kāi)始順序遍歷鏈表。

如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個(gè)數(shù)據(jù)對(duì)應(yīng)的結(jié)點(diǎn)，并將其從原來(lái)的位置刪除，然后再插入到鏈表的頭部。

如果此數(shù)據(jù)沒(méi)有在緩存鏈表中，又可以分為兩種情況：如果此時(shí)緩存未滿，則將此結(jié)點(diǎn)直接插入到鏈表的頭部；如果此時(shí)緩存已滿，則鏈表尾結(jié)點(diǎn)刪除，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部。

? ? ? ? 因?yàn)椴还芫彺嬗袥](méi)有滿，我們都需要遍歷一遍鏈表，所以這種基于鏈表的實(shí)現(xiàn)思路，緩存訪問(wèn)的時(shí)間復(fù)雜度為 O(n)。實(shí)際上，我們可以繼續(xù)優(yōu)化這個(gè)實(shí)現(xiàn)思路，比如引入散列表（Hash table）來(lái)記錄每個(gè)數(shù)據(jù)的位置，將緩存訪問(wèn)的時(shí)間復(fù)雜度降到 O(1)。

手寫(xiě)鏈表的注意事項(xiàng)

? ? ? ? 寫(xiě)鏈表代碼是最考驗(yàn)邏輯思維能力的。因?yàn)殒湵泶a到處都是指針的操作、邊界條件的處理，稍有不慎就容易產(chǎn)生 Bug。鏈表代碼寫(xiě)得好壞，可以看出一個(gè)人寫(xiě)代碼是否夠細(xì)心，考慮問(wèn)題是否全面，思維是否縝密。

• 利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度
• 注意邊界值的處理，要把正常情況和以下特殊情況都分析檢驗(yàn)一下：鏈表為空，鏈表只包含一個(gè)結(jié)點(diǎn)，鏈表只包含兩個(gè)結(jié)點(diǎn)等等。
• 多畫(huà)圖舉例 。把它畫(huà)在紙上，釋放一些腦容量，留更多的給邏輯思考，這樣就會(huì)感覺(jué)到思路清晰很多。
• 多寫(xiě)多練。寫(xiě)個(gè)十幾遍，背也能背下來(lái)了，當(dāng)然并不提倡背，重要的還是記住算法思想

public class LinkedListAlgo {/*** 單鏈表反轉(zhuǎn)* 時(shí)間復(fù)雜度 O(n)* 空間復(fù)雜度 O(1)*/public static Node reverseList(Node head){Node prev = null;Node curr = head;Node next;//其實(shí)就是prev跟著curr，往后走while(curr != null){//注意這樣記憶，順序上一行的右邊就是下一行的左邊next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}/*** 尋找中間結(jié)點(diǎn)* @return 如果鏈表為偶數(shù)，返回中間偏右那個(gè)結(jié)點(diǎn)* 時(shí)間復(fù)雜度 O(n)* 空間復(fù)雜度 O(1)*/public static Node findMiddleNode(Node head){if(head == null){return null;}Node fast = head;Node slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}/*** 鏈表中環(huán)的檢測(cè)* @return 環(huán)的長(zhǎng)度* 時(shí)間復(fù)雜度 O(n)* 空間復(fù)雜度 O(1)*/public static int checkCircle(Node head){Node fast = head;Node slow = head;int count = 0;boolean meet = false;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;//相遇，說(shuō)明有環(huán)。meet == true開(kāi)始計(jì)數(shù)if(fast == slow){meet = true;}if(meet){//因?yàn)閒ast是slow的2倍，所以fast和slow再次相遇時(shí)，正好fast跑2圈，slow跑了一圈，也就是環(huán)的長(zhǎng)度if(count != 0 && fast == slow){return count;}count++;}}return 0;}/*** 合并兩個(gè)有序鏈表* @param head1 從小到大排序的鏈表* @param head2 從小到大排序的鏈表* @return 合并后的鏈表* 時(shí)間復(fù)雜度 O(m+n) ？？*/public static Node mergeSortList(Node head1, Node head2){//引入一個(gè)哨兵。來(lái)避免下面還要判斷頭結(jié)點(diǎn)的問(wèn)題Node soldier = new Node(0, null);Node node = soldier;Node n1 = head1;Node n2 = head2;while (n1 != null && n2 != null){if(n1.data < n2.data){node.next = n1;n1 = n1.next;}else {node.next = n2;n2 = n2.next;}node = node.next;}//此時(shí)說(shuō)明有一個(gè)鏈表走到頭，另一個(gè)鏈表還沒(méi)走到頭if(n1 != null){node.next = n1;}if(n2 != null){node.next = n2;}//哨兵的下一個(gè)節(jié)點(diǎn)就是合并后的頭結(jié)點(diǎn)return soldier.next;}/*** 刪除鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)* @param k 從1開(kāi)始數(shù)*/public static Node removeNode(Node head, int k){Node fast = head;int n = 1;while (fast != null && n < k){fast = fast.next;n++;}//fast走到頭，說(shuō)明鏈表的長(zhǎng)度還不到k。直接返回原鏈表if(fast == null){return head;}Node slow = head;Node prev = null;while (fast.next != null){fast = fast.next;prev = slow;slow = slow.next;}//prev指的是要?jiǎng)h除的第k個(gè)節(jié)點(diǎn)前的那個(gè)節(jié)點(diǎn)if(prev == null){head = head.next;}else {prev.next = prev.next.next;}return head;}public static void main(String[] args) {//Node list = createNodeList();Node list = new Node(2,null);Node list2 = new Node(3,null);list.next = list2;printAll(list);Node node = removeNode(list, 1);printAll(node);//Node middleNode = findMiddleNode(list);//printAll(middleNode);//Node reverseList = reverseList(list);//printAll(reverseList);//System.out.println("環(huán)的長(zhǎng)度為 "+ checkCircle(list));//printAll(mergeSortList(createNodeList(), createNodeList2()));}public static class Node {private int data;private Node next;public Node(int data, Node next) {this.data = data;this.next = next;}}/*** 根據(jù)頭節(jié)點(diǎn)逐個(gè)打印所有結(jié)點(diǎn)*/public static void printAll(Node list){Node p = list;while (p != null){System.out.print(p.data + " ");p = p.next;}System.out.println();}public static Node createNode(int value) {return new Node(value, null);}public static Node createNodeList() {Node a = createNode(1);Node b = createNode(2);a.next = b;Node c = createNode(3);b.next = c;Node d = createNode(4);c.next = d;Node e = createNode(5);d.next = e;Node f = createNode(6);e.next = f;//形成環(huán)//f.next = c;return a;}public static Node createNodeList2() {Node a = createNode(1);Node b = createNode(4);a.next = b;Node c = createNode(6);b.next = c;Node d = createNode(7);c.next = d;Node e = createNode(9);d.next = e;return a;}

總結(jié)

以上是生活随笔為你收集整理的（二）链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。