數(shù)組快還是鏈表快這個(gè)問(wèn)題我在技術(shù)社區(qū)看到過(guò)無(wú)數(shù)次新手在面試前背得滾瓜爛熟但真到了寫(xiě)代碼選型的時(shí)候反而猶豫不決。其實(shí)這不怪大家因?yàn)槭忻嫔辖^大部分教材都在講時(shí)間復(fù)雜度把這句話直接等同于數(shù)組查找快、鏈表增刪快但實(shí)際工程里根本不是這么回事。我做后端開(kāi)發(fā)這些年因?yàn)檫x錯(cuò)數(shù)據(jù)結(jié)構(gòu)導(dǎo)致接口超時(shí)、內(nèi)存暴漲的情況遇到過(guò)不少今天就把這些經(jīng)驗(yàn)和踩過(guò)的坑一次說(shuō)清楚結(jié)合真實(shí)的代碼場(chǎng)景聊聊數(shù)組和鏈表到底該怎么選。這篇文章適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的初學(xué)者也適合寫(xiě)了幾年業(yè)務(wù)代碼但沒(méi)系統(tǒng)梳理過(guò)底層機(jī)制的朋友。我會(huì)先從存儲(chǔ)模型講起再對(duì)比查找和增刪的實(shí)際表現(xiàn)分析Cache和內(nèi)存分配這些容易被忽略的維度最后給出一套可以直接套用的選型決策方法并附上幾個(gè)完整的實(shí)戰(zhàn)案例復(fù)盤。1. 速度與靈活的博弈本質(zhì)兩種截然不同的存儲(chǔ)模型要理解數(shù)組和鏈表為什么有這么大差異得先看清楚它們?cè)趦?nèi)存里到底是怎么存放的。很多人以為這只是API用法的區(qū)別其實(shí)從內(nèi)存布局那一刻起兩者的命運(yùn)就已經(jīng)注定了。1.1 數(shù)組的連續(xù)內(nèi)存模型與隨機(jī)訪問(wèn)的數(shù)學(xué)基礎(chǔ)數(shù)組在內(nèi)存中分配的是一段連續(xù)的空間每個(gè)元素緊挨著前一個(gè)元素存放。假設(shè)一個(gè)整型數(shù)組的首地址是base每個(gè)元素占size字節(jié)那么第i個(gè)元素的地址就是addr(i) base i * size這是一個(gè)純粹的乘法加加法運(yùn)算CPU執(zhí)行這個(gè)計(jì)算只需要幾個(gè)時(shí)鐘周期。所以數(shù)組訪問(wèn)任意位置的時(shí)間復(fù)雜度是O(1)這個(gè)O(1)背后沒(méi)有隱藏常數(shù)就是實(shí)打?qū)嵉囊淮螌ぶ?。這也是為什么數(shù)組能夠支持隨機(jī)訪問(wèn)——你可以像抽撲克牌一樣直接抽第N張不需要從第一張開(kāi)始數(shù)。我在實(shí)際項(xiàng)目中經(jīng)常利用這個(gè)特性做索引映射。比如一個(gè)電商訂單狀態(tài)枚舉有10種取值我直接建一個(gè)長(zhǎng)度為10的數(shù)組用狀態(tài)碼當(dāng)下標(biāo)O(1)就能拿到狀態(tài)描述文案和對(duì)應(yīng)的處理策略對(duì)象連HashMap都不用。這種場(chǎng)景下數(shù)組的簡(jiǎn)潔和高效沒(méi)有任何其他數(shù)據(jù)結(jié)構(gòu)能比。1.2 鏈表的節(jié)點(diǎn)分散存儲(chǔ)與逐級(jí)跳轉(zhuǎn)邏輯鏈表則完全相反它的節(jié)點(diǎn)在內(nèi)存中是分散存放的。每個(gè)節(jié)點(diǎn)除了保存自己的數(shù)據(jù)還要存一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針單鏈表或者同時(shí)還存指向前一個(gè)節(jié)點(diǎn)的指針雙向鏈表。鏈表的節(jié)點(diǎn)之間靠這些指針手拉手串成一條鏈。正因?yàn)檫@種松散的物理結(jié)構(gòu)鏈表天然不具備隨機(jī)訪問(wèn)能力。你想訪問(wèn)第5個(gè)節(jié)點(diǎn)必須從頭節(jié)點(diǎn)出發(fā)依次經(jīng)過(guò)第1個(gè)、第2個(gè)、第3個(gè)、第4個(gè)節(jié)點(diǎn)才能到達(dá)第5個(gè)。這就是為什么鏈表的隨機(jī)訪問(wèn)時(shí)間復(fù)雜度是O(n)——找第n個(gè)節(jié)點(diǎn)需要走n步。但有失必有得。鏈表的節(jié)點(diǎn)可以隨時(shí)從內(nèi)存中申請(qǐng)、隨時(shí)釋放不需要提前知道總共有多少數(shù)據(jù)也不需要預(yù)留一整塊連續(xù)空間。對(duì)于數(shù)據(jù)量未知、頻繁增刪的場(chǎng)景這種靈活性是數(shù)組給不了的。舉一個(gè)最直觀的例子你在寫(xiě)一個(gè)日志采集器每秒會(huì)有幾百條數(shù)據(jù)進(jìn)來(lái)又不能提前預(yù)估總量。用數(shù)組的話你得反復(fù)擴(kuò)容用鏈表就可以來(lái)一條插一條毫無(wú)壓力。1.3 數(shù)組查詢快、鏈表增刪快到底哪里不對(duì)我在開(kāi)頭說(shuō)過(guò)這句話有問(wèn)題現(xiàn)在拆開(kāi)來(lái)看。嚴(yán)格來(lái)說(shuō)這個(gè)說(shuō)法只在掩蓋了常數(shù)因子的情況下成立。數(shù)組查詢確實(shí)是O(1)這點(diǎn)沒(méi)問(wèn)題但鏈表增刪并不是所有情況下都O(1)——它只有在已經(jīng)持有目標(biāo)節(jié)點(diǎn)的指針時(shí)插入和刪除才是O(1)。如果你只知道要?jiǎng)h除第5個(gè)節(jié)點(diǎn)那你得先花O(n)的時(shí)間遍歷過(guò)去然后才能O(1)地刪除。所以鏈表增刪的完整復(fù)雜度其實(shí)是O(n) O(1)前面的遍歷開(kāi)銷往往才是大頭。而且數(shù)組的插入刪除之所以慢是因?yàn)樾枰嵋圃?。但這個(gè)搬移是內(nèi)存連續(xù)拷貝現(xiàn)代CPU和操作系統(tǒng)對(duì)連續(xù)的塊狀拷貝做了大量?jī)?yōu)化速度非?？臁Ｎ以趯?shí)際項(xiàng)目中測(cè)試過(guò)在百萬(wàn)級(jí)數(shù)據(jù)量的數(shù)組頭部插入一個(gè)元素整個(gè)過(guò)程耗時(shí)才幾百微秒遠(yuǎn)沒(méi)有想象中那么可怕。真正可怕的是鏈表在遍歷過(guò)程中因?yàn)榫彺娌幻性斐傻男阅軗p耗這個(gè)后面詳細(xì)說(shuō)。所以在做選型之前請(qǐng)務(wù)必把數(shù)組查詢快、鏈表增刪快這句話從腦子里刪掉換成更準(zhǔn)確的版本數(shù)組適合讀多寫(xiě)少、下標(biāo)訪問(wèn)明確的場(chǎng)景鏈表適合寫(xiě)多讀少、且操作位置已知的場(chǎng)景。這才是兩者博弈的真正邊界。2. 核心差異深度拆解時(shí)間復(fù)雜度的誤讀與真實(shí)的性能瓶頸既然基礎(chǔ)的存儲(chǔ)模型清楚了接下來(lái)就該聊聊實(shí)際操作中最容易出問(wèn)題的部分。很多朋友背了時(shí)間復(fù)雜度就覺(jué)得自己懂了但一寫(xiě)代碼就發(fā)現(xiàn)運(yùn)行結(jié)果和理論完全對(duì)不上。這里面的關(guān)鍵因素包括常數(shù)因子、Cache利用率和內(nèi)存分配策略。2.1 增刪操作的真實(shí)開(kāi)銷為什么要隱藏遍歷代價(jià)先看兩段代碼同樣是往頭部插入一個(gè)元素。數(shù)組版本def insert_at_head(arr, value): arr.insert(0, value) return arr鏈表版本假設(shè)手寫(xiě)了節(jié)點(diǎn)類class Node: def __init__(self, value): self.value value self.next None def insert_at_head(head, value): new_node Node(value) new_node.next head return new_node從代碼行數(shù)上看鏈表版本更復(fù)雜但它的插入操作本身只是兩個(gè)賦值語(yǔ)句沒(méi)有元素搬移。數(shù)組版本雖然只調(diào)用了Python的insert但底層需要把所有的已有元素都往后挪一格。但請(qǐng)注意鏈表可以這么做的前提是我已經(jīng)持有頭節(jié)點(diǎn)的引用。如果我要在鏈表中間某個(gè)位置插入節(jié)點(diǎn)還是得先從頭遍歷到那個(gè)位置。所以在實(shí)際工程中單純比較插入一個(gè)節(jié)點(diǎn)的整體代價(jià)鏈表未必比數(shù)組快。尤其當(dāng)鏈表很長(zhǎng)、插入位置靠近尾部時(shí)遍歷的代價(jià)會(huì)把插入的收益完全抵消。我建議大家在評(píng)估增刪性能時(shí)一定要帶入完整的操作鏈路來(lái)看查找定位 插入/刪除。數(shù)組的定位是O(1)搬移是O(n)但搬移系數(shù)極小鏈表的定位是O(n)插入是O(1)但每一步遍歷都可能Cache Miss。這就是為什么工程實(shí)踐中數(shù)組的中間插入往往反而比鏈表更快。2.2 CPU緩存友好性為何連續(xù)內(nèi)存是性能放大器這個(gè)點(diǎn)知道的人不多但在大數(shù)據(jù)量場(chǎng)景下它決定了程序的生死。現(xiàn)代CPU在讀取主存數(shù)據(jù)時(shí)并不是一個(gè)字節(jié)一個(gè)字節(jié)地讀而是按緩存行常見(jiàn)為64字節(jié)批量加載。當(dāng)你訪問(wèn)數(shù)組的第一個(gè)元素時(shí)CPU會(huì)把包含該元素的一整段內(nèi)存都加載到高速緩存里。接下來(lái)你訪問(wèn)數(shù)組的第二個(gè)、第三個(gè)元素這些數(shù)據(jù)已經(jīng)在緩存里了訪問(wèn)速度極快。鏈表呢每個(gè)節(jié)點(diǎn)分散在內(nèi)存的各個(gè)角落CPU加載頭節(jié)點(diǎn)的時(shí)候只能順帶把頭節(jié)點(diǎn)附近的64字節(jié)加載進(jìn)來(lái)但鏈表的下一個(gè)節(jié)點(diǎn)可能根本不在這個(gè)范圍內(nèi)于是又得從主存重新讀取。這個(gè)緩存Miss→內(nèi)存加載的過(guò)程非常昂貴比CPU直接命中緩存慢了數(shù)十倍甚至上百倍。說(shuō)一個(gè)我實(shí)際測(cè)過(guò)的數(shù)據(jù)用雙重循環(huán)遍歷一個(gè)100萬(wàn)節(jié)點(diǎn)的數(shù)組和等長(zhǎng)鏈表數(shù)組遍歷耗時(shí)約2ms鏈表遍歷耗時(shí)約40ms。同樣都是O(n)的時(shí)間復(fù)雜度但因?yàn)榫彺婷新实牟町悓?shí)際性能差了20倍。如果你選錯(cuò)了結(jié)構(gòu)可能業(yè)務(wù)邏輯一層沒(méi)變服務(wù)端到了高并發(fā)時(shí)直接被打爆。2.3 內(nèi)存分配策略與空間開(kāi)銷鏈表的隱性成本數(shù)組在創(chuàng)建時(shí)一次性申請(qǐng)一整塊內(nèi)存空間利用率幾乎是100%只有尾部可能留一點(diǎn)擴(kuò)容余量。鏈表每個(gè)節(jié)點(diǎn)除了數(shù)據(jù)本身還要額外存儲(chǔ)指針。在64位系統(tǒng)里一個(gè)指針占8字節(jié)。假設(shè)你的數(shù)據(jù)是一個(gè)int4字節(jié)那么單鏈表節(jié)點(diǎn)至少額外多花8字節(jié)雙向鏈表則是16字節(jié)。這意味著鏈表的有效載荷率可能連三分之一都不到。舉個(gè)真實(shí)例子。我之前維護(hù)過(guò)一個(gè)實(shí)時(shí)推薦系統(tǒng)用戶特征存儲(chǔ)用了一個(gè)很大的雙向鏈表結(jié)構(gòu)。當(dāng)時(shí)內(nèi)存占用居高不下排查后發(fā)現(xiàn)節(jié)點(diǎn)里的指針開(kāi)銷占了總內(nèi)存的60%以上。后來(lái)?yè)Q成數(shù)組加索引映射直接把內(nèi)存占用砍掉了將近一半性能還提升了三成。所以當(dāng)你在做選型時(shí)不要只看時(shí)間維度空間維度同樣關(guān)鍵。尤其在云環(huán)境里內(nèi)存就是錢。多出來(lái)幾十GB的節(jié)點(diǎn)指針開(kāi)銷意味著你要多買一臺(tái)機(jī)器。2.4 擴(kuò)容機(jī)制對(duì)數(shù)組的影響動(dòng)態(tài)數(shù)組的隱藏“寫(xiě)放大”很多人擔(dān)心數(shù)組容量固定、不能動(dòng)態(tài)增長(zhǎng)就用鏈表來(lái)避免這個(gè)問(wèn)題。但大多數(shù)語(yǔ)言的標(biāo)準(zhǔn)庫(kù)都提供了動(dòng)態(tài)數(shù)組比如Java的ArrayList、Python的list、C的vector它們會(huì)在容量不足時(shí)自動(dòng)申請(qǐng)一塊更大的內(nèi)存并把舊數(shù)據(jù)拷貝過(guò)去。這個(gè)擴(kuò)容動(dòng)作是有代價(jià)的。以Java ArrayList為例默認(rèn)擴(kuò)容為原來(lái)的1.5倍整體拷貝的時(shí)間復(fù)雜度是O(n)。但由于擴(kuò)容是按幾何級(jí)數(shù)增長(zhǎng)的平攤下來(lái)每次插入操作的平均成本依然是O(1)。這就是均攤復(fù)雜度的概念鏈表的插入雖然是嚴(yán)格的O(1)但在實(shí)際表現(xiàn)上動(dòng)態(tài)數(shù)組的插入并不會(huì)比鏈表慢太多。不過(guò)有一種場(chǎng)景必須警惕如果你的數(shù)據(jù)結(jié)構(gòu)反復(fù)在填滿→擴(kuò)容→拷貝之間循環(huán)比如數(shù)組容量到達(dá)邊界后每插入一個(gè)元素就觸發(fā)一次1.5倍擴(kuò)容拷貝的浪費(fèi)會(huì)變得非常可觀。此時(shí)可以預(yù)估數(shù)據(jù)量提前指定初始容量這個(gè)問(wèn)題就完美解決了。3. 實(shí)戰(zhàn)選型指南一套可以直接抄的決策方法理論講再多最終還是要落到我這段代碼到底該用哪個(gè)。我在總結(jié)了自己的實(shí)踐和團(tuán)隊(duì)踩坑經(jīng)驗(yàn)后整理出一套決策流程你照著判斷就行基本不會(huì)出大錯(cuò)。3.1 五步選型決策法從數(shù)據(jù)規(guī)模到操作模式第一步先回答這個(gè)問(wèn)題你最頻繁的操作是什么是按下標(biāo)讀還是按值查是頭尾增刪還是中間插入不同的操作組合指向的結(jié)構(gòu)完全不同。第二步評(píng)估數(shù)據(jù)規(guī)模與增長(zhǎng)模式。如果數(shù)據(jù)量是萬(wàn)級(jí)以下說(shuō)實(shí)話數(shù)組和鏈表在性能上的差距可以忽略選寫(xiě)起來(lái)最順手的就行。但數(shù)據(jù)量到百萬(wàn)級(jí)以上Cache的差異就會(huì)被放大到不可忽視的程度。第三步考慮內(nèi)存的敏感性。如果運(yùn)行環(huán)境內(nèi)存吃緊優(yōu)先選數(shù)組。鏈表的節(jié)點(diǎn)指針開(kāi)銷在這種場(chǎng)景下就是奢侈品。第四步看并發(fā)需求。鏈表在并發(fā)修改時(shí)只需鎖住局部節(jié)點(diǎn)而數(shù)組的搬移操作往往需要鎖更大的范圍。如果你的系統(tǒng)是寫(xiě)多讀少的高并發(fā)場(chǎng)景鏈表可能更友好。第五步問(wèn)一句有沒(méi)有現(xiàn)成的庫(kù)函數(shù)能簡(jiǎn)化實(shí)現(xiàn)很多語(yǔ)言的標(biāo)準(zhǔn)庫(kù)已經(jīng)對(duì)常見(jiàn)結(jié)構(gòu)做了大量?jī)?yōu)化自己能手寫(xiě)的鏈表在大多數(shù)情況下并不比庫(kù)實(shí)現(xiàn)好。千萬(wàn)別為了炫技去重復(fù)造輪子。3.2 高頻場(chǎng)景一圖流讀多寫(xiě)少用數(shù)組寫(xiě)多讀少看位置為了說(shuō)得更直觀我把常見(jiàn)場(chǎng)景和推薦結(jié)構(gòu)整理成一張表。你在選型的時(shí)候可以直接對(duì)號(hào)入座。場(chǎng)景特征推薦結(jié)構(gòu)核心理由按下標(biāo)高頻隨機(jī)訪問(wèn)數(shù)組O(1)隨機(jī)訪問(wèn)Cache友好按值查詢但數(shù)據(jù)量小數(shù)組或HashMap小數(shù)據(jù)量差異可忽略數(shù)組更省內(nèi)存只在頭部插入/刪除鏈表頭節(jié)點(diǎn)直接操作無(wú)搬移代價(jià)只在尾部追加動(dòng)態(tài)數(shù)組均攤O(1)Cache效率高中間位置頻繁插入刪除鏈表持有位置指針插入無(wú)需搬移元素中間位置訪問(wèn)為主數(shù)組鏈表遍歷到中間成本太高數(shù)據(jù)量不可預(yù)估且增長(zhǎng)快鏈表免擴(kuò)容無(wú)限增長(zhǎng)需要LRU淘汰等復(fù)雜操作鏈表哈希表經(jīng)典組合O(1)定位與增刪3.3 工程中最重要的選型原則永遠(yuǎn)以實(shí)測(cè)數(shù)據(jù)為準(zhǔn)表格給的是通用經(jīng)驗(yàn)但通用經(jīng)驗(yàn)擋不住奇葩的業(yè)務(wù)場(chǎng)景。我見(jiàn)過(guò)一個(gè)極端案例某團(tuán)隊(duì)處理一批平均長(zhǎng)度只有3的短列表但調(diào)用頻率極高每秒鐘幾百萬(wàn)次循環(huán)。這種場(chǎng)景下任何理論分析都不如直接跑個(gè)基準(zhǔn)測(cè)試有意義。我個(gè)人的習(xí)慣是拿真實(shí)數(shù)據(jù)量做一次micro-benchmark把兩種結(jié)構(gòu)的讀寫(xiě)時(shí)延分別打出來(lái)。別憑感覺(jué)也別完全相信教科書(shū)上的結(jié)論。因?yàn)榻炭茣?shū)上沒(méi)有考慮你機(jī)器的緩存大小、內(nèi)存帶寬、編譯器優(yōu)化等級(jí)這些變量。推薦一個(gè)很樸素的測(cè)試方法同一個(gè)算法用數(shù)組和鏈表各寫(xiě)一遍喂相同的數(shù)據(jù)跑100次取平均耗時(shí)。如果你連寫(xiě)兩版都嫌麻煩那就直接記住一條經(jīng)驗(yàn)法則——拿不準(zhǔn)的時(shí)候先用數(shù)組實(shí)測(cè)不行再換。數(shù)組的動(dòng)態(tài)擴(kuò)展和隨機(jī)訪問(wèn)能力讓它成為大多數(shù)場(chǎng)景下的安全默認(rèn)項(xiàng)這也符合Java、Python等語(yǔ)言設(shè)計(jì)者的選擇。4. 三個(gè)實(shí)戰(zhàn)案例復(fù)盤從接口超時(shí)到內(nèi)存爆炸再到LRU優(yōu)化很多人覺(jué)得數(shù)據(jù)結(jié)構(gòu)選型離日常業(yè)務(wù)很遠(yuǎn)實(shí)際上關(guān)系非常大。我把這幾年經(jīng)歷過(guò)的三個(gè)真實(shí)問(wèn)題寫(xiě)出來(lái)你看看是不是很有共鳴。4.1 案例一百萬(wàn)級(jí)用戶在線列表為什么接口總是超時(shí)有一年我們做一個(gè)社區(qū)產(chǎn)品需要一個(gè)當(dāng)前在線用戶的列表每個(gè)用戶上線就加入、下線就移除同時(shí)前端還要高頻地按照用戶ID查詢某個(gè)人是否在線。最初版本用的是鏈表每次上線尾部插入O(1)下線需要遍歷找到對(duì)應(yīng)節(jié)點(diǎn)再移除在線人數(shù)峰值百萬(wàn)級(jí)結(jié)果每次下線操作都要遍歷很長(zhǎng)的鏈路CPU直接被打滿接口頻繁超時(shí)。排查之后把結(jié)構(gòu)換成了數(shù)組哈希表索引數(shù)組負(fù)責(zé)按下標(biāo)快速遍歷所有在線用戶哈希表負(fù)責(zé)用戶ID到數(shù)組下標(biāo)的映射。這樣一來(lái)查詢?cè)诰€K不需要遍歷下線K通過(guò)哈希表O(1)定位到數(shù)組下標(biāo)再把數(shù)組最后一個(gè)元素挪過(guò)來(lái)補(bǔ)位同時(shí)更新哈希表。整個(gè)刪改過(guò)程均攤O(1)接口超時(shí)問(wèn)題當(dāng)場(chǎng)消失。4.2 案例二圖像處理像素隊(duì)列為何內(nèi)存直接翻倍另一個(gè)項(xiàng)目里需要緩存一批待處理的圖像行數(shù)據(jù)每個(gè)像素行是一個(gè)結(jié)構(gòu)體整體用一個(gè)鏈表存放。隨著任務(wù)堆積進(jìn)程內(nèi)存漲到了預(yù)期值的兩倍還多直接觸發(fā)容器OOMKilled。原因就是每個(gè)鏈表節(jié)點(diǎn)在64位系統(tǒng)下有16字節(jié)的指針開(kāi)銷而每行像素?cái)?shù)據(jù)本身也就幾十字節(jié)。算下來(lái)無(wú)效內(nèi)存超過(guò)了50%。后來(lái)我把鏈表改成預(yù)分配容量的數(shù)組結(jié)構(gòu)配合環(huán)形隊(duì)列指針來(lái)管理頭尾位置內(nèi)存占用立刻恢復(fù)正常處理吞吐也提升了將近27%。這個(gè)案例讓我意識(shí)到內(nèi)存碎片和指針開(kāi)銷不是紙上談兵的教科書(shū)概念而是真金白銀的運(yùn)維賬單。4.3 案例三LRU緩存淘汰算法為什么必須是鏈表哈希表最后說(shuō)一個(gè)正面案例。在做一個(gè)商品詳情頁(yè)的本地緩存時(shí)需要實(shí)現(xiàn)LRU最近最少使用淘汰策略。核心要求是get和put操作都必須接近O(1)。如果只用哈希表雖然可以用時(shí)間戳排序做淘汰但每次淘汰都要掃描所有鍵O(n)的代價(jià)在緩存大了以后沒(méi)法接受。正確的解法就是哈希表雙向鏈表的黃金組合。哈希表負(fù)責(zé)O(1)定位到某個(gè)key對(duì)應(yīng)的鏈表節(jié)點(diǎn)雙向鏈表負(fù)責(zé)維護(hù)訪問(wèn)順序每次訪問(wèn)一個(gè)節(jié)點(diǎn)就把它搬到鏈表頭部淘汰時(shí)直接從尾部刪除。節(jié)點(diǎn)里同時(shí)存key和數(shù)據(jù)這樣就可以在刪除鏈表尾部節(jié)點(diǎn)時(shí)同步刪除哈希表中的記錄。這個(gè)組合方案能用不到30行代碼實(shí)現(xiàn)一個(gè)百萬(wàn)級(jí)容量的LRU而且讀寫(xiě)都是嚴(yán)格O(1)。這就是鏈表不可替代的價(jià)值所在——在某些場(chǎng)景里它和哈希表配合能產(chǎn)生112的效果。5. 新手常踩的坑與我的最終建議做技術(shù)分享這些年我見(jiàn)過(guò)太多人在數(shù)組和鏈表上栽跟頭。有些坑是理解層面的有些是實(shí)際操作層面的這里集中梳理一下你寫(xiě)代碼的時(shí)候多留個(gè)心眼。5.1 誤區(qū)清單這幾條最容易讓人翻車第一條否認(rèn)數(shù)組的動(dòng)態(tài)擴(kuò)容能力?？傆腥苏f(shuō)數(shù)組長(zhǎng)度固定數(shù)據(jù)多了沒(méi)法用但動(dòng)態(tài)數(shù)組幾乎在所有主流語(yǔ)言里都是標(biāo)配能自動(dòng)擴(kuò)容。除非需要極致的內(nèi)存控制和性能優(yōu)化否則這個(gè)擔(dān)心是多余的。第二條忽略鏈表的順序遍歷成本。有些同學(xué)在鏈表里做按索引查詢操作還覺(jué)得這是O(1)。實(shí)際上要訪問(wèn)第500個(gè)節(jié)點(diǎn)你就得老老實(shí)實(shí)從第1個(gè)走到第500個(gè)這在數(shù)據(jù)量大時(shí)是災(zāi)難。第三條不知道鏈表的額外內(nèi)存開(kāi)銷。我見(jiàn)過(guò)有人為了省幾MB內(nèi)存選擇鏈表結(jié)果反而多了幾十MB的指針開(kāi)銷。選型之前先算一筆內(nèi)存賬這很重要。第四條頻繁擴(kuò)容導(dǎo)致性能抖動(dòng)。動(dòng)態(tài)數(shù)組雖然均攤性能不錯(cuò)但如果初始容量設(shè)置得太小數(shù)據(jù)量又非常大擴(kuò)容拷貝的浪費(fèi)會(huì)集中爆發(fā)。我建議預(yù)估一個(gè)寬松的初始容量寧多勿少。第五條標(biāo)記刪除與真正的節(jié)點(diǎn)釋放混為一談。有些語(yǔ)言的鏈表刪除只是把指針跳過(guò)節(jié)點(diǎn)本身需要異步釋放或內(nèi)存回收。如果只改指針不管內(nèi)存長(zhǎng)時(shí)間運(yùn)行后容易出現(xiàn)內(nèi)存泄漏。5.2 用一句話判定你的場(chǎng)景該選誰(shuí)如果只記住一句話我建議記住這個(gè)下標(biāo)訪問(wèn)多、內(nèi)存敏感、數(shù)據(jù)規(guī)模大選數(shù)組位置已知的頻繁插入刪除、數(shù)據(jù)量動(dòng)態(tài)變化大、不需要按下標(biāo)訪問(wèn)選鏈表。這句話基本上覆蓋了九成以上的場(chǎng)景。如果還是拿不準(zhǔn)那就再加一個(gè)判斷維度你的操作是讀多寫(xiě)少還是寫(xiě)多讀少。前者無(wú)腦選數(shù)組后者再往下細(xì)分——如果寫(xiě)操作集中在頭部或尾部而且能直接拿到節(jié)點(diǎn)引用選鏈表如果寫(xiě)操作分散在中間且無(wú)法持有位置還是老老實(shí)實(shí)數(shù)組或跳表。5.3 我的真實(shí)體會(huì)不要神化任何結(jié)構(gòu)最后說(shuō)點(diǎn)掏心窩的話。數(shù)據(jù)結(jié)構(gòu)選型本質(zhì)上是在時(shí)間、空間、實(shí)現(xiàn)復(fù)雜度之間做權(quán)衡沒(méi)有哪個(gè)結(jié)構(gòu)是全能的。數(shù)組和鏈表就像工具箱里的兩種扳手各有各的適用螺絲。我見(jiàn)過(guò)把鏈表用得極漂亮的高性能緩存也見(jiàn)過(guò)用數(shù)組輕松搞定千萬(wàn)級(jí)數(shù)據(jù)排序的精妙方案。從我個(gè)人經(jīng)驗(yàn)來(lái)看在小數(shù)據(jù)量的場(chǎng)景里糾結(jié)數(shù)組還是鏈表純屬浪費(fèi)時(shí)間。真正需要仔細(xì)權(quán)衡的是那些數(shù)據(jù)量在百萬(wàn)級(jí)、操作頻率極高的核心鏈路。這種時(shí)候花半小時(shí)做個(gè)基準(zhǔn)測(cè)試遠(yuǎn)比背一百遍原理有用。用數(shù)據(jù)說(shuō)話是這一行最靠譜的工作方式。