1. 從鏈表到容器為什么這章是所有算法課的基石如果你翻過《算法第4版》Algorithms_4th大概率會(huì)和我一樣在第一章就被三種最基礎(chǔ)的抽象數(shù)據(jù)類型ADT卡住過——Bags背包、Queues隊(duì)列、Stacks棧。表面上它們只是三種裝東西的盒子但如果你把整本書往后翻會(huì)發(fā)現(xiàn)后面所有的高級(jí)結(jié)構(gòu)樹、圖、哈希表、排序算法、最短路徑……幾乎每一個(gè)都在這三種容器之上做文章。這一章不是熱身而是整本教材真正的起跑線。這一章解決的核心問題很樸素在Java里寫算法時(shí)我們?cè)趺创鎯?chǔ)、怎么訪問數(shù)據(jù)數(shù)組可以嗎可以但數(shù)組的長(zhǎng)度固定、插入刪除麻煩而且一旦涉及泛型就有各種類型擦除的坑。鏈表呢鏈表靈活但手動(dòng)管理指針容易出錯(cuò)。于是這章給出了三個(gè)標(biāo)準(zhǔn)答案——Bag、Queue、Stack用它們各自的訪問順序規(guī)則覆蓋算法中最常見的幾種數(shù)據(jù)訪問模式先進(jìn)先出、后進(jìn)先出、只收集不回頭。適合誰(shuí)來讀說實(shí)話不只是正在啃這本書的學(xué)生。哪怕你是工作兩三年的開發(fā)者如果你發(fā)現(xiàn)自己在寫代碼時(shí)經(jīng)常糾結(jié)到底是拿數(shù)組還是拿鏈表、這個(gè)隊(duì)列到底該用LinkedList還是ArrayDeque那你在這章里會(huì)找到一套特別清晰的判斷依據(jù)。我當(dāng)年是工作后回頭補(bǔ)算法基礎(chǔ)才讀的這章讀完之后最大的感受是以前寫業(yè)務(wù)代碼靠感覺選容器現(xiàn)在有了一整套理論支撐。這章的原理解釋非常教科書但正因?yàn)榻炭茣芏嗉?xì)節(jié)都是暗線。我會(huì)把這章拆成兩條線來講一條是設(shè)計(jì)思路解釋為什么這章要把三種容器放在一起講另一條是實(shí)現(xiàn)細(xì)節(jié)把教科書里點(diǎn)到為止的鏈表實(shí)現(xiàn)、動(dòng)態(tài)數(shù)組擴(kuò)容、迭代器設(shè)計(jì)這些坑都給填上。在動(dòng)手過一遍源碼之后你會(huì)發(fā)現(xiàn)這一章的量其實(shí)很足足夠你消化一陣子的。2. 三種容器設(shè)計(jì)思路拆解訪問順序決定一切2.1 為什么是包、隊(duì)列、棧三兄弟一起講在講解實(shí)現(xiàn)之前我想先聊聊一個(gè)很多人忽略的問題為什么這三種容器要放在同一節(jié)里它們的用途差異其實(shí)非常大但存在一個(gè)共同的數(shù)學(xué)結(jié)構(gòu)——它們都是集合都支持兩個(gè)最基本的操作插入insert和刪除delete。區(qū)別只有一個(gè)刪除哪一個(gè)。Bag只插入不刪除或者說不關(guān)心刪除順序。Queue刪除最先進(jìn)來的那一個(gè)FIFOFirst-In-First-Out。Stack刪除最近進(jìn)來的那一個(gè)LIFOLast-In-First-Out。你看僅僅一個(gè)刪除策略的差異就讓三個(gè)容器走上了完全不同的道路。這就好比餐廳的出餐口你排隊(duì)點(diǎn)單先來的先做這是隊(duì)列你往書包里塞書最后塞進(jìn)去的反而最容易抽出來這是棧你把一堆物品丟進(jìn)一個(gè)袋子之后想拿哪個(gè)拿哪個(gè)這是背包。教材把這三種容器放在一起是想讓你建立一種抽象思維底層數(shù)據(jù)結(jié)構(gòu)鏈表或數(shù)組是通用的但通過不同的接口暴露就變成了行為完全不同的容器。這也是面向?qū)ο笤O(shè)計(jì)里封裝和接口隔離最經(jīng)典的教學(xué)案例。后面你寫代碼時(shí)如果需要一個(gè)只進(jìn)不出的緩沖區(qū)不該用List而應(yīng)該用Bag如果需要處理嵌套結(jié)構(gòu)優(yōu)先想到Stack如果需要處理公平調(diào)度優(yōu)先想到Queue。2.2 數(shù)組實(shí)現(xiàn) vs 鏈表實(shí)現(xiàn)的核心取舍教科書在實(shí)現(xiàn)這三種容器時(shí)用了兩種底層物理結(jié)構(gòu)數(shù)組Array和鏈表Linked List。這是算法生涯里第一個(gè)重要的二選一我建議你從這章開始就建立一套自己的判斷體系。數(shù)組實(shí)現(xiàn)的優(yōu)勢(shì)是內(nèi)存連續(xù)索引訪問O(1)CPU緩存友好。劣勢(shì)是插入和刪除非尾部是O(n)且擴(kuò)容時(shí)需要整體搬運(yùn)。鏈表實(shí)現(xiàn)的優(yōu)勢(shì)是插入和刪除已知前驅(qū)節(jié)點(diǎn)時(shí)是O(1)無需連續(xù)內(nèi)存擴(kuò)容零成本。劣勢(shì)是隨機(jī)訪問O(n)且每個(gè)節(jié)點(diǎn)要額外存儲(chǔ)下一個(gè)節(jié)點(diǎn)的指針內(nèi)存占用更高。一個(gè)很關(guān)鍵的點(diǎn)教材里沒有明說但實(shí)現(xiàn)里隱含了用數(shù)組實(shí)現(xiàn)棧是最優(yōu)解用鏈表實(shí)現(xiàn)棧和隊(duì)列是最符合直覺的解用鏈表實(shí)現(xiàn)Bag是最省事的解。為什么因?yàn)闂５牟迦牒蛣h除都發(fā)生在同一端棧頂數(shù)組的尾部操作就是O(1)配合動(dòng)態(tài)擴(kuò)容均攤成本也很低而隊(duì)列需要在兩端操作數(shù)組在頭部刪除是O(n)除非用環(huán)形數(shù)組鏈表則天然適合。這些結(jié)論我建議你親手寫一遍實(shí)現(xiàn)才會(huì)有體感。2.3 泛型和迭代器這章里的隱形主角如果你只是粗讀一遍很容易把泛型Generics和迭代器Iterator當(dāng)成Java的附屬語(yǔ)法略過。但實(shí)際上這一章是整本書第一次系統(tǒng)性使用泛型和迭代器的地方也是大多數(shù)初學(xué)者第一次在這里被編譯錯(cuò)誤勸退的地方。先說泛型。為什么容器必須用泛型因?yàn)槿绻萜髦荒艽鍻bject你取出來就得強(qiáng)轉(zhuǎn)強(qiáng)轉(zhuǎn)就容易ClassCastException而且代碼里全是臟兮兮的強(qiáng)制轉(zhuǎn)換。用了泛型容器在編譯期就能保證類型安全。但Java的泛型是類型擦除實(shí)現(xiàn)的這里有一個(gè)特別容易踩的坑你不能直接創(chuàng)建泛型數(shù)組。例如T[] items new T[10]是無法編譯的。教材里的解法是創(chuàng)建Object數(shù)組然后強(qiáng)轉(zhuǎn)T[] items (T[]) new Object[10]。這個(gè)寫法會(huì)有個(gè)編譯警告但確實(shí)是通用解法。你千萬別試圖用new T[10]那是過不了的。再說迭代器。為什么容器要實(shí)現(xiàn)Iterable接口因?yàn)镴ava的for (String s : stack)語(yǔ)法糖本質(zhì)上調(diào)用的就是容器的iterator()方法。這個(gè)設(shè)計(jì)把遍歷邏輯從容器中解耦出來你可以為同一個(gè)容器實(shí)現(xiàn)多個(gè)不同的迭代器比如正序遍歷、反序遍歷。教材里通過內(nèi)部類實(shí)現(xiàn)迭代器并且強(qiáng)調(diào)了一個(gè)重要的設(shè)計(jì)原則迭代器應(yīng)該是一個(gè)快照或者說它維護(hù)的是當(dāng)前遍歷的狀態(tài)但容器本身不知道迭代器的存在。有一個(gè)細(xì)節(jié)值得注意迭代器里的remove()方法教材里直接拋了UnsupportedOperationException這是有意為之。因?yàn)楹芏鄶?shù)據(jù)結(jié)構(gòu)比如Bag壓根不支持刪除與其讓迭代器提供無用操作不如直接禁用。這個(gè)設(shè)計(jì)思路后來在Java標(biāo)準(zhǔn)庫(kù)中被廣泛采納。3. 核心實(shí)現(xiàn)細(xì)節(jié)與實(shí)操要點(diǎn)3.1 鏈表的節(jié)點(diǎn)設(shè)計(jì)內(nèi)部類 vs 靜態(tài)內(nèi)部類實(shí)現(xiàn)鏈表容器時(shí)第一個(gè)要決定的事就是節(jié)點(diǎn)類怎么寫。教材里用了非靜態(tài)內(nèi)部類private class Node我見過不少讀者照著敲代碼也能跑通但不清楚為什么不用靜態(tài)內(nèi)部類。非靜態(tài)內(nèi)部類有個(gè)隱藏特性每個(gè)實(shí)例都持有外部類實(shí)例的引用。也就是說每個(gè)Node節(jié)點(diǎn)都認(rèn)識(shí)它所屬的容器。這在鏈表容器里不是必需的反而會(huì)帶來兩個(gè)問題一是內(nèi)存多占一個(gè)引用字段二是可能造成外部類無法被GC回收如果Node被錯(cuò)誤地泄露出去。但如果改成靜態(tài)內(nèi)部類private static class Node就沒有這個(gè)問題。你可能想問那為什么教材要用非靜態(tài)的因?yàn)榻虒W(xué)代碼追求的是讀起來簡(jiǎn)單。對(duì)一個(gè)學(xué)習(xí)者來說Node直接訪問外部類的成員變量是直觀的但實(shí)際上靜態(tài)內(nèi)部類也能做到通過參數(shù)傳遞。我的建議是如果你在寫自己的庫(kù)用靜態(tài)內(nèi)部類如果你在照著教材學(xué)習(xí)可以先用非靜態(tài)的理解之后改成靜態(tài)的體會(huì)一下差異。這里還有一個(gè)細(xì)節(jié)節(jié)點(diǎn)類里存的item和next字段在教材里沒有加final。但如果你認(rèn)真考慮過會(huì)意識(shí)到next其實(shí)在節(jié)點(diǎn)生命周期內(nèi)最多改變一次甚至不改變所以用final修飾next在邏輯上更嚴(yán)謹(jǐn)。有些同學(xué)喜歡寫防御性代碼這個(gè)習(xí)慣在算法學(xué)習(xí)中越早養(yǎng)成越好。3.2 動(dòng)態(tài)數(shù)組擴(kuò)容與縮容均攤分析的藝術(shù)數(shù)組實(shí)現(xiàn)棧的核心難點(diǎn)不在壓棧和彈棧本身——那就是賦值和指針移動(dòng)——而在數(shù)組的擴(kuò)容和縮容策略。這里有兩個(gè)經(jīng)典問題什么時(shí)候擴(kuò)容什么時(shí)候縮容教材給出的答案是插入時(shí)如果數(shù)組滿了擴(kuò)容為原來的2倍彈出時(shí)如果元素個(gè)數(shù)只有數(shù)組長(zhǎng)度的1/4縮容為原來的一半。這個(gè)2倍擴(kuò)、四分之一縮的設(shè)計(jì)很多讀者第一次看會(huì)覺得很奇怪為什么不滿了就加10個(gè)為什么彈到一半就縮其實(shí)這背后是均攤分析Amortized Analysis的思想。如果我們每次滿就加一個(gè)固定值比如10那么連續(xù)插入n個(gè)元素的時(shí)間是11...11011...110...最壞情況是O(n^2)因?yàn)槊看螖U(kuò)容都要把舊數(shù)據(jù)復(fù)制到新數(shù)組。但如果按2倍擴(kuò)容擴(kuò)容次數(shù)只有O(log n)次總復(fù)制次數(shù)是124...n2n-1均攤到每次插入就是O(1)。為什么縮容選擇1/4而不是1/2因?yàn)槿绻麧M時(shí)擴(kuò)容到2倍而你在容量為2N時(shí)彈到N就立刻縮容那緊接著你壓入一個(gè)元素又會(huì)觸發(fā)擴(kuò)容到2N這樣反復(fù)在閾值附近操作會(huì)導(dǎo)致頻繁擴(kuò)容/縮容形成所謂的抖動(dòng)thrashing。把觸發(fā)線調(diào)到1/4留出了一倍的緩沖空間就避免了這個(gè)問題。這是一個(gè)非常優(yōu)雅的工程設(shè)計(jì)你以后寫任何動(dòng)態(tài)數(shù)組包括Java的ArrayList都可以參考這個(gè)思路。3.3 可迭代容器設(shè)計(jì)內(nèi)部迭代器與Fail-Fast機(jī)制讓容器實(shí)現(xiàn)IterableT接口需要在內(nèi)部提供一個(gè)IteratorT的匿名類或內(nèi)部類。這里面有幾個(gè)實(shí)操細(xì)節(jié)值得展開。第一迭代器應(yīng)該記錄當(dāng)前節(jié)點(diǎn)的引用而不是返回一個(gè)數(shù)組的副本。很多新手寫迭代器時(shí)會(huì)先把所有元素復(fù)制到一個(gè)臨時(shí)數(shù)組再遍歷數(shù)組——這雖然能跑但空間復(fù)雜度O(n)就白費(fèi)了而且違背了惰性求值的初衷。正確的做法是棧的迭代器用一個(gè)Node current first隊(duì)列迭代器用Node current first數(shù)組實(shí)現(xiàn)的棧則用一個(gè)int i N每次調(diào)用next()時(shí)相應(yīng)移動(dòng)。第二迭代器是否需要fail-fast快速失敗Java標(biāo)準(zhǔn)庫(kù)里的ArrayList、HashMap等容器都有fail-fast機(jī)制如果在迭代過程中檢測(cè)到結(jié)構(gòu)性修改比如調(diào)用add或remove迭代器會(huì)拋出ConcurrentModificationException。教材里的迭代器沒有做這個(gè)檢查因?yàn)檫@是教學(xué)代碼追求最小實(shí)現(xiàn)。但如果你在生產(chǎn)環(huán)境寫自己的容器我強(qiáng)烈建議加上modCount計(jì)數(shù)器的檢查。這可以幫你盡早發(fā)現(xiàn)一邊遍歷一邊修改這種隱蔽的bug否則會(huì)出現(xiàn)難以定位的間歇性錯(cuò)誤。第三迭代器的hasNext()和next()方法要對(duì)邊界情況做防御。比如next()在沒有更多元素時(shí)應(yīng)該拋NoSuchElementException而不是返回 null 或數(shù)組越界。這個(gè)細(xì)節(jié)雖然小但寫容器庫(kù)時(shí)接口約定必須明確。3.4 對(duì)象游離GC視角下的隱藏內(nèi)存泄漏這一節(jié)我要特別強(qiáng)調(diào)一個(gè)章節(jié)里容易一眼帶過的知識(shí)點(diǎn)——對(duì)象游離Loitering。教材里這樣描述在棧的pop()實(shí)現(xiàn)中如果不把彈出的數(shù)組項(xiàng)設(shè)為null那么數(shù)組依然持有這個(gè)對(duì)象的引用即使外部已經(jīng)不再使用它GC也無法回收它。聽起來很簡(jiǎn)單但實(shí)際開發(fā)中這個(gè)問題極其隱蔽。我給你講一個(gè)真實(shí)場(chǎng)景。某次我在寫一個(gè)簡(jiǎn)單的事件處理器時(shí)用了一個(gè)數(shù)組實(shí)現(xiàn)的棧來暫存事件對(duì)象。彈出后我直接用return items[--N]沒有把items[N]置為null。功能一切正常但服務(wù)跑了一個(gè)月后內(nèi)存曲線穩(wěn)步上升最終OOM。排查了很久才發(fā)現(xiàn)那些已經(jīng)被彈出的事件對(duì)象因?yàn)閿?shù)組中還保留著引用GC永遠(yuǎn)無法回收它們。這就是游離對(duì)象導(dǎo)致的內(nèi)存泄漏——不是傳統(tǒng)意義上無法訪問的泄漏而是其實(shí)還能訪問但永遠(yuǎn)不再有用的泄漏。所以無論你用鏈表還是數(shù)組實(shí)現(xiàn)容器只要元素是從容器中移除的都應(yīng)該立刻清除引用。鏈表實(shí)現(xiàn)中將first指向下一個(gè)節(jié)點(diǎn)并置空舊節(jié)點(diǎn)的item數(shù)組實(shí)現(xiàn)中將items[N]置為null。這個(gè)習(xí)慣養(yǎng)成了你能在未來的開發(fā)中避開一個(gè)大坑。4. 實(shí)操過程與核心環(huán)節(jié)實(shí)現(xiàn)4.1 手寫鏈表實(shí)現(xiàn)的棧從節(jié)點(diǎn)類到迭代器現(xiàn)在我們把理論落到代碼上。教材里用鏈表實(shí)現(xiàn)棧我在這里給出一個(gè)完整可運(yùn)行的版本加了詳細(xì)的注釋并在實(shí)現(xiàn)上做了一些生產(chǎn)級(jí)優(yōu)化。import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedStackItem implements IterableItem { private NodeItem first; // 棧頂元素 private int n; // 元素?cái)?shù)量 private static class NodeItem { private Item item; private NodeItem next; } public LinkedStack() { first null; n 0; } public boolean isEmpty() { return first null; } public int size() { return n; } public void push(Item item) { NodeItem oldFirst first; first new NodeItem(); first.item item; first.next oldFirst; n; } public Item pop() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); Item item first.item; first first.next; n--; return item; } public Item peek() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); return first.item; } public IteratorItem iterator() { return new LinkedIterator(first); } private class LinkedIterator implements IteratorItem { private NodeItem current; public LinkedIterator(NodeItem first) { current first; } public boolean hasNext() { return current ! null; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item current.item; current current.next; return item; } } }幾個(gè)關(guān)鍵點(diǎn)我再重復(fù)強(qiáng)調(diào)一遍Node用靜態(tài)內(nèi)部類避免持有外部類引用。predicate檢查isEmpty()要在pop()和peek()中做不然你會(huì)在空棧上解引用空指針。迭代器是單鏈方向從棧頂往棧底遍歷。這個(gè)順序?qū)碚f是符合直覺的后進(jìn)先出。push操作里用oldFirst暫存舊節(jié)點(diǎn)再新建節(jié)點(diǎn)指向它。頭插法O(1)。這里pop()我其實(shí)沒有把first.item置為null因?yàn)殒湵砉?jié)點(diǎn)會(huì)被GC回收如果外部不再引用。但如果你保存了彈出的Node引用請(qǐng)記得置空。這就是我在上一節(jié)提到的游離對(duì)象問題在鏈表實(shí)現(xiàn)中的變體。4.2 數(shù)組實(shí)現(xiàn)的棧動(dòng)態(tài)擴(kuò)容和縮容的完整代碼鏈表實(shí)現(xiàn)的棧邏輯簡(jiǎn)單但每個(gè)節(jié)點(diǎn)要存一個(gè)引用內(nèi)存開銷大。數(shù)組實(shí)現(xiàn)更緊湊但需要處理擴(kuò)容。下面是完整的數(shù)組棧實(shí)現(xiàn)import java.util.Iterator; import java.util.NoSuchElementException; public class ResizingArrayStackItem implements IterableItem { private Item[] items; private int n; public ResizingArrayStack() { items (Item[]) new Object[2]; n 0; } public boolean isEmpty() { return n 0; } public int size() { return n; } private void resize(int capacity) { Item[] temp (Item[]) new Object[capacity]; for (int i 0; i n; i) { temp[i] items[i]; } items temp; } public void push(Item item) { if (n items.length) { resize(2 * items.length); } items[n] item; } public Item pop() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); Item item items[n - 1]; items[n - 1] null; // 避免對(duì)象游離 n--; if (n 0 n items.length / 4) { resize(items.length / 2); } return item; } public IteratorItem iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements IteratorItem { private int i n; public boolean hasNext() { return i 0; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return items[--i]; } } }這份代碼里有幾個(gè)細(xì)節(jié)值得你反復(fù)琢磨resize方法里創(chuàng)建新數(shù)組后要手動(dòng)拷貝所有舊元素。這里我用了一個(gè)循環(huán)某些書籍里會(huì)建議用System.arraycopy性能更好。但在學(xué)習(xí)階段手寫循環(huán)更能加深理解。push里的擴(kuò)容條件是n items.length。注意此時(shí)數(shù)組中所有位置都已被占用再插入就必須擴(kuò)容。擴(kuò)容倍率2這是時(shí)間與空間的平衡點(diǎn)。擴(kuò)容后舊數(shù)組會(huì)被GC回收新的數(shù)組長(zhǎng)度是原來的2倍。pop里的縮容條件是n 0 n items.length / 4。這里有一個(gè)n 0的守衛(wèi)防止空棧時(shí)items.length為0的情況理論上不會(huì)發(fā)生因?yàn)槌跏既萘渴?但防御性代碼總是好的。迭代器實(shí)現(xiàn)的是從棧頂?shù)綏５椎谋闅v。因?yàn)闂Ｊ荓IFO迭代器方向應(yīng)該從最近的元素開始也就是數(shù)組尾部。我記得有一次寫迭代器時(shí)方向搞反了導(dǎo)致輸出順序完全不對(duì)調(diào)試了半天才發(fā)現(xiàn)。這個(gè)方向細(xì)節(jié)很值得記下來。4.3 隊(duì)列的鏈表實(shí)現(xiàn)頭尾雙指針怎么維護(hù)隊(duì)列比棧多一個(gè)限制入隊(duì)在一端出隊(duì)在另一端。用鏈表實(shí)現(xiàn)時(shí)我們需要維護(hù)兩個(gè)指針first指向隊(duì)頭出隊(duì)端last指向隊(duì)尾入隊(duì)端。public class LinkedQueueItem implements IterableItem { private NodeItem first; private NodeItem last; private int n; private static class NodeItem { private Item item; private NodeItem next; } public boolean isEmpty() { return first null; } public int size() { return n; } public void enqueue(Item item) { NodeItem oldLast last; last new NodeItem(); last.item item; last.next null; if (isEmpty()) { first last; } else { oldLast.next last; } n; } public Item dequeue() { if (isEmpty()) throw new NoSuchElementException(Queue underflow); Item item first.item; first first.next; n--; if (isEmpty()) { last null; // 避免游離對(duì)象 } return item; } }有個(gè)細(xì)節(jié)我特別想強(qiáng)調(diào)在enqueue時(shí)如果隊(duì)列為空first和last必須同時(shí)指向新節(jié)點(diǎn)。如果不處理這個(gè)分支老節(jié)點(diǎn)oldLast是null直接oldLast.next last就會(huì)空指針。這個(gè)邊界條件是鏈表隊(duì)列最常見的bug來源。在dequeue時(shí)刪除的是first節(jié)點(diǎn)。但要注意如果刪除后隊(duì)列空了last仍然指向舊的隊(duì)尾節(jié)點(diǎn)這個(gè)引用是游離的必須把last置為null。這就是對(duì)象游離在鏈表實(shí)現(xiàn)中的又一個(gè)變體。教科書代碼里我見過不處理這個(gè)分支的版本功能上不報(bào)錯(cuò)但嚴(yán)格來說內(nèi)存管理有瑕疵。隊(duì)列的迭代器實(shí)現(xiàn)和棧類似只是從first開始遍歷。這里不再贅述。4.4 背包的實(shí)現(xiàn)最簡(jiǎn)容器但隱藏了迭代器的強(qiáng)大背包Bag是所有容器里最簡(jiǎn)單的一種只往里加?xùn)|西不給刪除的方法。但別小看它在后面的圖算法和統(tǒng)計(jì)計(jì)算中背包非常常用——比如你可能需要收集圖中所有頂點(diǎn)的鄰居然后遍歷一遍統(tǒng)計(jì)信息但你并不關(guān)心訪問順序。public class BagItem implements IterableItem { private NodeItem first; private int n; private static class NodeItem { private Item item; private NodeItem next; } public void add(Item item) { NodeItem oldFirst first; first new NodeItem(); first.item item; first.next oldFirst; n; } public boolean isEmpty() { return first null; } public int size() { return n; } public IteratorItem iterator() { return new LinkedIterator(first); } }背包的add直接采用頭插法不需要維護(hù)last指針因?yàn)樵L問順序不重要。你注意到?jīng)]有它的實(shí)現(xiàn)其實(shí)和鏈表?xiàng)５膒ush一模一樣。唯一的區(qū)別是接口層沒有pop方法。這正好印證了我前邊說的底層物理結(jié)構(gòu)可以復(fù)用但通過接口約束出不同的抽象數(shù)據(jù)類型。背包在算法中的一個(gè)典型應(yīng)用場(chǎng)景是圖的鄰接表。當(dāng)你用BagInteger[] adj來存儲(chǔ)每個(gè)頂點(diǎn)的相鄰頂點(diǎn)時(shí)你只關(guān)心能枚舉所有鄰居不關(guān)心鄰居的順序。這時(shí)候用一個(gè)只支持添加和遍歷的容器從語(yǔ)義上就避免了誤用。我在實(shí)際項(xiàng)目里見過用ArrayList當(dāng)只讀集合的代碼但從接口層面就禁止刪除明顯是更好的設(shè)計(jì)。5. 常見問題與排查技巧實(shí)錄5.1 編譯錯(cuò)誤泛型數(shù)組創(chuàng)建失敗現(xiàn)象T[] arr new T[10]編譯直接報(bào)錯(cuò)。原因Java的泛型通過類型擦除實(shí)現(xiàn)運(yùn)行時(shí)并不知道T的具體類型因此無法創(chuàng)建泛型數(shù)組。解法可以按下面幾種方式來// 方法1創(chuàng)建Object數(shù)組后強(qiáng)轉(zhuǎn)教材做法 T[] arr (T[]) new Object[10]; // 方法2使用Array.newInstance反射創(chuàng)建更靈活但更繁瑣 T[] arr (T[]) Array.newInstance(clazz, capacity);我建議初學(xué)階段用方法1簡(jiǎn)潔且夠用。要提醒的是強(qiáng)轉(zhuǎn)會(huì)有一個(gè)unchecked警告這是正常的。但如果你用方法2雖然能拿到精確類型的數(shù)組代碼復(fù)雜度會(huì)上升學(xué)習(xí)時(shí)沒必要引入。還有一個(gè)小技巧如果你在類里聲明的是private T[] items在構(gòu)造函數(shù)里可以用items (T[]) new Object[capacity]。這個(gè)寫法在resize方法里同樣適用。5.2 空棧/空隊(duì)操作NoSuchElementException還是返回null現(xiàn)象在空棧上調(diào)用pop()在空隊(duì)列上調(diào)用dequeue()程序崩潰或行為異常。原因?qū)崿F(xiàn)時(shí)沒有做空指針檢查或者檢查了但拋的異常不明確。解法我建議在pop()、peek()、dequeue()的開頭都顯式檢查isEmpty()如果為空則拋出NoSuchElementException。這樣做有兩個(gè)好處一是報(bào)錯(cuò)信息明確Stack underflow二是把異常行為統(tǒng)一到標(biāo)準(zhǔn)庫(kù)接口上——java.util.Stack的pop()在空棧時(shí)會(huì)拋EmptyStackException而java.util.ArrayDeque會(huì)拋NoSuchElementException。如果你在寫自己的容器庫(kù)遵循Java標(biāo)準(zhǔn)庫(kù)的異常約定是最好的選擇。5.3 迭代器中修改容器ConcurrentModificationException還是靜默錯(cuò)誤現(xiàn)象在遍歷一個(gè)棧/隊(duì)列的過程中突然插入或刪除了元素程序出現(xiàn)各種詭異行為。原因迭代器已經(jīng)保存了當(dāng)前節(jié)點(diǎn)的引用但容器結(jié)構(gòu)變了迭代器的狀態(tài)和容器不一致。解法如果你希望快速失敗可以在容器中維護(hù)一個(gè)modCount計(jì)數(shù)器每次結(jié)構(gòu)性修改push/pop/enqueue/dequeue都自增。迭代器保存創(chuàng)建時(shí)的modCount每次調(diào)用next()時(shí)檢查當(dāng)前的modCount是否一致不一致就拋ConcurrentModificationException。教材里省略了這個(gè)機(jī)制但Java標(biāo)準(zhǔn)庫(kù)ArrayList的做法就是這樣。如果你在學(xué)習(xí)階段就理解了這個(gè)設(shè)計(jì)以后看JDK源碼會(huì)輕松很多。5.4 鏈表 vs 數(shù)組的性能選擇什么場(chǎng)景選哪個(gè)這是我在評(píng)論區(qū)最常被問的問題。這里給一個(gè)比較直接的速查表場(chǎng)景推薦實(shí)現(xiàn)理由需要頻繁隨機(jī)訪問按下標(biāo)取元素?cái)?shù)組索引訪問O(1)頻繁在頭部插入/刪除鏈表頭部操作O(1)數(shù)組頭部操作O(n)頻繁在尾部插入/刪除數(shù)組均攤O(1)需要頻繁擴(kuò)容且不確定最終大小數(shù)組動(dòng)態(tài)擴(kuò)容均攤O(1)內(nèi)存敏感且節(jié)點(diǎn)數(shù)量巨大數(shù)組鏈表每個(gè)節(jié)點(diǎn)多一個(gè)引用字段需要頻繁合并兩個(gè)容器鏈表只需調(diào)整指針有一個(gè)經(jīng)驗(yàn)法則如果你不確定選哪個(gè)優(yōu)先用數(shù)組實(shí)現(xiàn)。因?yàn)閿?shù)組對(duì)CPU緩存友好在現(xiàn)代硬件上通常比鏈表快一個(gè)量級(jí)。鏈表的O(1)插入優(yōu)勢(shì)很多時(shí)候會(huì)被緩存不命中的代價(jià)抵消。這一點(diǎn)在后續(xù)學(xué)習(xí)樹和圖的時(shí)候會(huì)更明顯。5.5 對(duì)象游離導(dǎo)致的隱性內(nèi)存泄漏怎么排查排查內(nèi)存泄漏最直接的辦法就是用內(nèi)存分析工具比如VisualVM、MAT看堆轉(zhuǎn)儲(chǔ)。如果你發(fā)現(xiàn)一個(gè)數(shù)組容器里的對(duì)象遲遲不能被回收而代碼邏輯上它們已經(jīng)不再需要那十有八九就是對(duì)象游離問題?？梢园聪旅鎺撞娇焖倥挪闄z查所有pop()、dequeue()、remove()方法確認(rèn)刪除元素后是否將數(shù)組槽位置為null。檢查所有臨時(shí)引用是否清理干凈。比如你保存了Node引用刪除后要把node.item置為null。檢查容器縮容時(shí)擴(kuò)縮容方法是否完整拷貝有效元素并丟棄舊數(shù)組引用。我自己的習(xí)慣是寫完一個(gè)容器之后用-Xmx16m跑一個(gè)小堆內(nèi)存的測(cè)試腳本往里壓幾百萬個(gè)對(duì)象再全彈出來看內(nèi)存是否回落到初始水平。如果內(nèi)存不回落說明有游離引用。這個(gè)方法簡(jiǎn)單有效適合你自己寫容器的自測(cè)。5.6 邊寫邊測(cè)的單元測(cè)試模板最后分享一個(gè)我用來測(cè)試這些容器的單元測(cè)試模板。別小看測(cè)試這些容器雖然代碼不長(zhǎng)但邊界條件非常多。public class StackTest { Test public void testPushPopOrder() { LinkedStackInteger stack new LinkedStack(); stack.push(1); stack.push(2); stack.push(3); assertEquals(3, stack.pop().intValue()); assertEquals(2, stack.pop().intValue()); assertEquals(1, stack.pop().intValue()); assertTrue(stack.isEmpty()); } Test public void testResizingArrayStackManyElements() { ResizingArrayStackInteger stack new ResizingArrayStack(); for (int i 0; i 10000; i) { stack.push(i); } for (int i 9999; i 0; i--) { assertEquals(i, stack.pop().intValue()); } assertTrue(stack.isEmpty()); } Test(expected NoSuchElementException.class) public void testPopEmptyStack() { LinkedStackInteger stack new LinkedStack(); stack.pop(); } Test public void testQueueOrder() { LinkedQueueString queue new LinkedQueue(); queue.enqueue(a); queue.enqueue(b); queue.enqueue(c); assertEquals(a, queue.dequeue()); assertEquals(b, queue.dequeue()); assertEquals(c, queue.dequeue()); assertTrue(queue.isEmpty()); } Test public void testIterator() { LinkedStackInteger stack new LinkedStack(); stack.push(1); stack.push(2); int sum 0; for (int x : stack) { sum x; } assertEquals(3, sum); } }這套模板覆蓋了順序性、擴(kuò)容場(chǎng)景、空容器操作、迭代器四條基本路徑。你可以在這些基礎(chǔ)上增加性能測(cè)試比如壓入100萬個(gè)元素看耗時(shí)來對(duì)比鏈表和數(shù)組實(shí)現(xiàn)的差距。6. 從這章延伸出去你在為后面的算法鋪路講了這么多具體實(shí)現(xiàn)最后我想跳出來談?wù)勥@一章在更大知識(shí)圖譜中的位置。很多人學(xué)《算法第4版》會(huì)犯一個(gè)錯(cuò)誤急著往后翻圖算法和字符串算法覺得容器是常識(shí)不需要細(xì)看。但我可以負(fù)責(zé)任地說后面所有算法章節(jié)都會(huì)用到這章的知識(shí)而且用的方式往往是組合拳。圖算法里深度優(yōu)先搜索DFS本質(zhì)上就是用棧或遞歸遞歸就是隱式棧實(shí)現(xiàn)的廣度優(yōu)先搜索BFS則是用隊(duì)列實(shí)現(xiàn)的。你要是沒把棧和隊(duì)列的實(shí)現(xiàn)搞清楚后面理解DFS、BFS會(huì)非常吃力。堆排序、優(yōu)先隊(duì)列這些本質(zhì)上是在數(shù)組上實(shí)現(xiàn)的一棵完全二叉樹你在這一章學(xué)到的動(dòng)態(tài)數(shù)組擴(kuò)容和對(duì)象游離處理全部會(huì)復(fù)用到優(yōu)先隊(duì)列的實(shí)現(xiàn)中。符號(hào)表那章用鏈表實(shí)現(xiàn)順序查找其實(shí)就是這一章鏈表實(shí)現(xiàn)的直接延伸只是節(jié)點(diǎn)里多存了一個(gè)鍵值對(duì)。我自己學(xué)這章時(shí)做過一件小事把這三種容器的鏈表實(shí)現(xiàn)和數(shù)組實(shí)現(xiàn)各寫了一遍然后跑了一組對(duì)比測(cè)試記錄了插入10萬、100萬、1000萬個(gè)元素的時(shí)間。結(jié)果讓我印象深刻在1000萬規(guī)模下數(shù)組實(shí)現(xiàn)比鏈表實(shí)現(xiàn)快大約一個(gè)數(shù)量級(jí)。這個(gè)數(shù)據(jù)讓我以后在選擇容器時(shí)有了更強(qiáng)的直覺。我建議你也做一次類似的實(shí)驗(yàn)這會(huì)讓你對(duì)算法的常數(shù)因子有切身體會(huì)。這章還有一個(gè)價(jià)值我很少見人提起但它實(shí)際很重要它是對(duì)抽象數(shù)據(jù)類型這個(gè)概念最好的入門訓(xùn)練。理解了物理存儲(chǔ)結(jié)構(gòu)鏈表/數(shù)組和邏輯訪問規(guī)則LIFO/FIFO/無序是兩回事你就擁有了和數(shù)據(jù)結(jié)構(gòu)的本質(zhì)打交道的能力。以后你看任何高級(jí)數(shù)據(jù)結(jié)構(gòu)比如跳表、紅黑樹、B樹本質(zhì)上都是某種物理結(jié)構(gòu)服務(wù)于某種訪問規(guī)則的產(chǎn)物。有了這個(gè)思維模型你會(huì)走得更遠(yuǎn)。