用鏈表的目的是什麼？省空間還是省時間？

12-31

正在學數據結構，學到鏈表這裡，正在寫一個稀疏矩陣的東西創建一個用鏈表表示的稀疏矩陣的時候書上方法：先設一個輔助數組，長度為讀入矩陣最大可能維數（#define的），用來放頭結點，讓後讀入非零元素的時候再一個個申請空間，插入鏈表。網上搜的一個程序的辦法：乾脆先設一個長度很長的數組，頭結點，非零元都放在裡面。我自己的想法。。所有節點都一個個申請空間，，，我想知道的是：用鏈表的目的是什麼？我以為是利用零碎空間：數組需要一大片連續空間，而鏈表是散落的，靠指針連著。而上面兩個方法都預設了數組，這是為啥呢？那直接用數組不就好了嗎？鏈表的目的是什麼？？

鏈表的優點除了「插入刪除不需要移動其他元素」之外，還在於它是一個局部化結構。就是說當你拿到鏈表的一個 node 之後，不需要太多其它數據，就可以完成插入，刪除的操作。而其它的數據結構不行。比如說 array，你只拿到一個 item 是斷不敢做插入刪除的。

當然了，局部化這個好處只有 intrusive 鏈表才有，就是必須 prev/next 嵌入在數據結構中。像 STL 和 Java 那種設計是失敗了。

另外多說幾句：

我不認為鏈表是 abstract data structure。Linked-list 裡面的 linked 就表明了實現手段，也就不抽象了。有人說用 array 可以實現鏈表，我說這個有點牽強：因為 array 是一個近似於底層 memory 的結構。如果你給 array 寫一個 allocator 相當於 CRT 的 malloc，然後把 array index 當 pointer 來用，那什麼數據結構都能用 array 來實現。所以能用 array 來實現並不是 abstract 與否的標準。

通常我們把 array 作為和其它結構並列的數據結構來討論問題的時候，我們指在程序的較高層次上也按照簡單的連續空間來解釋 array。如果我們像用底層內存實現高層 structure 那樣來解釋 array，這個討論也就沒有 common ground 了。（讀過 GEB 的人會發現這裡我們就遇到了 cross-level reference 的問題。）

先說空間問題：鏈表不會節省空間，原因：鏈表有結點。單向鏈表有指向下一個元素的結點；單項循環鏈表的最後一個元素有指向第一個元素的結點；雙向循環鏈表有指向前一個元素的結點和指向後一個元素的結點。所以鏈表不會節省空間。再說時間問題：如果只是插入和刪除操作，那麼不會移動元素，所以會節省時間，數組的插入和刪除是要移動元素的（插入和刪除最後一個元素不移動）；鏈表的查找操作是從第一個元素開始，所以相對數組要耗時間（數組直接就可以查找到）。有時間上圖好了。。。這個是Java版的數據結構，c的我忘了，答主不好意思。。。。。。

（注釋：現在知乎的平均知識水平開始堪憂了啊，非要我亮了身份你們才相信我比你們更懂演算法和編程么……這麼簡單的問題匿名答一下都不行了現在……https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8Linked list 中英文鏈接都給你們，有什麼不會的自己看維基，裡面寫的多清楚，不要再在這兒和我糾結了好么！）

你犯了常識性錯誤。

這裡的鏈表是一種抽象的數據結構，每個節點有信息和下一個節點的地址，和怎麼實現半毛錢關係也沒有。鏈表當然也可以用數組實現，也可以用STL的vector，都不用動態allocate。書上和網上的做法都行。

（當然我覺得主要是翻譯的問題……不知道為啥把這兩個詞都叫鏈表……）

之所以需要兩個數組，其實是因為稀疏矩陣本身的有效節點不多。通過兩個數組確定矩陣的列和行的頭結點，可以便於查找。

書上的方法可行，但是沒有什麼現實意義。因為如果我還要依賴一個輔助數組的話，靈活性欠佳。

因為C語言中，數組必須在編譯時就確定長度。非常非常不方便。

&> 書上方法：先設一個輔助數組，長度為讀入矩陣最大可能維數（#define的），用來放頭結點，

&> 讓後讀入非零元素的時候再一個個申請空間，插入鏈表。

正好前一段時間也做了一個實現稀疏矩陣的十字鏈表，請參照下述位置：

https://github.com/xiaowing/libxw

我的實現中，頭結點和稀疏矩陣的非零節點都是作為同樣的「節點」來考慮的。

當然，我這個實現中還包含了內存的統一管理，請參考。

歡迎和我一起討論，你可以提Issue。

當你需要把xx元素移到第xx位時，你就體會到鏈表的好了。

事實上通常的做法是先申請一塊連續數據區存數據，再把數據區的地址存成鏈表進行管理，就跟你碰到的例子一樣。

不建議邊做鏈表邊申請空間，這樣的空間不連續，訪問效率低，而且你刪除元素還必須記得銷毀空間，否則內存泄露就不好了。

鏈表的用處是在特定應用場景下省時間。基本上鏈表不能省空間。

比如對鏈表在任意位置插入和刪除是O(1)的，而數組做不到這一點。

說到這裡，想起來在Quora上見到過一個高票（似乎是吧，記不清了）傻逼危言聳聽地說：

鏈表跟數組比毫無好處！鏈表的隨機插入也是O(n)的！我做實驗證明了的！

然後他的實驗方法是搞個鏈表，每次隨機一個下標，在那個下標處插入一個值，重複多次，測量運行時間。

好奇的話可以想想他錯在哪裡，或者我們口語里討論「隨機插入」的複雜度的時候是不是其實有一點點歧義呢。

再說另一個問題，太多回答在這裡糾結數組和鏈表的精確定義了。挺蛋疼的。

其實你對著計算機的多級存儲結構去想，這描述根本精確不了。你們所說的數組的連續內存塊根本不是物理上連續的，頁表都給你吃了？你們所說的鏈表的內存動態分配其實中間也經過了libc和操作系統的層層轉包……你們看的演算法都不會在描述演算法的時候把附加的所有實現細節描述進來，演算法本來就不是這麼描述的。反過來，其實每個演算法是對運行的機器有一些基本的假設，你給它提供滿足基本假設的環境，它就能運行了。比如用數組存儲，你需要的基本假設是你有一塊邏輯上連續，可以隨機訪問的存儲空間；而用鏈表存儲的時候，你需要的基本假設是你可以malloc, free和使用指針。

從這個角度來看，題主的數組模擬鏈表，只要能滿足鏈表需要的基本假設就行了。當然如果要性能也不出問題，那麼就要性能也滿足相應的條件。

弄幾個數組，通過記下標的方式來指向特定元素，可以認為是在硬體的虛存管理機制上面又套了一層「虛擬地址」的映射，所以這麼一看，指針是有了的。並且malloc也有，因為只要按順序分配就行了。

——但是等等！沒有free！所以回頭一看，題主的數組模擬鏈表確實是有資源泄漏的（反覆插入刪除節點，數組就爆了）。所以題主你需要考慮一下這個問題是不是需要解決。一個簡單的辦法是實現成雙鏈表，然後刪除節點的時候順便把目前地址最大的節點「移動」過來並且更新所有指向它的reference。另一個辦法是用另一個鏈表去維護所有的「未分配空間」，這樣的話malloc也得改一下（每次從未分配空間的鏈表裡拿節點）。

所以我覺得你們去糾結「這個是不是鏈表」，不如去想想「鏈表到底是什麼」，可能收穫會更多一點。

其實你的問題大概就是——為什麼我們要創造和使用數據結構？

很簡單，它能夠和演算法配合，滿足我們理解，編程和效率的需要。一個人類創造的工具。

工程上用鏈表來表達稀疏矩陣，可能是演算法上需要頻繁的插入或刪除非零項吧。但很多情況下，稀疏矩陣的非零項只是係數會變化，所以用數組來表示更合適, 常用的方法有CSR，而且在用GPU實現和稀疏矩陣有關的演算法時，CSR更能體現GPU的價值。如：

double* pNonZeroItems; //所有的非零項

double* pJ; //每個非零項對應的Column位置。

double* pI; //每行第一個元素在pJ上的起始位置。

矩陣X乘以向量V可以這樣來寫,

for(int iDOF = 0; iDOF &< N; iDOF++)

{

double lRowSum = 0;

int lRowStart = pI[iDOF];

int lRowEnd = pI[iDOF + 1];

for(int jDOF = lRowStart; jDOF &< lRowEnd; ++jDOF)

lRowSum += pNonZeroItems[jDOF] * V[pJ[jDOF]];

}

插入刪除不需要移動其他元素，是鏈表最大的特點

補充一點鏈表內存分配。鏈表使用不當很容易造成內存碎片。在實際工作中，鏈表頭跟鏈表實體有時候是分開的，比如16位元組的頭，一個指向下一個鏈表頭next指正，一個指向實體，addr，這個時候頭大小固定，而且站空間很少，如果數量是可知的，比如1000個以下，那麼直接用數組，才16k空間，即便10萬個，也才1.6m。這樣好處是不要內存分配，避免碎片。雖然預留一個大數組會有點浪費，但是如果有內存分配，浪費可能更多。還有一個好處是便於調試，看下這個數組就好了，尤其遇到內存錯亂的時候。昨天剛剛處理了一個搞了幾天沒解決的bug，後來用gdb p變數名就解決了(一個大struct)。還有一個變通是成組分配，比如1000個鏈表頭分配一次。最好是鏈表頭只分配，不釋放。

對於鏈表頭跟鏈表體在一起的，如果是固定長度，也用成組分配，也做成只申請，不釋放，自己維護一個free的鏈表即可。

如果鏈表體變長的，比如內存分配器，分配內存塊就是變長的，建議使用分級內存分配，比如2m，4k，2k以下，如果可以，盡量別釋放內存。

通常來講，鏈表可以避免數組申請整塊內存時out of memory的弊端。

方便被插入

鏈表!=用結構體/指針，類/引用實現的鏈表

都不省，鏈表是一種數據結構，它的優點是動態管理長度，可以任意定義節點數量，另外就是進行插入操作的複雜度較低。

至於為什麼你的書上用數組實現，因為鏈表只是個抽象數據結構並沒有定義實現方法，只要滿足鏈表定義那就是鏈表。

至於用數組實現的鏈表比普通數組的優勢，就是在尾部以外的地方插入新元素的時候複雜度比數組要低。

稀疏矩陣的特點就是數據量少。如果你有一個100x100的矩陣只有一個元素，相比於造一個100x100的二維數組，用鏈表表示稀疏矩陣只要一個單位的空間，你說哪個更省空間呢？所以說這個是按照數據特性選擇最優數據結構的問題。

如果你要比隨機讀取的時間複雜度，二維數組是常量時間，鏈表表示可能需要O(n)（在矩陣大小是nxn的前提下）。但是考慮到是稀疏矩陣，所以鏈表訪問時間實際上會非常小，小到平均情況就只要遍歷幾個，也就是可以近似認為為常量時間。同時在空間佔用上，鏈表表示稀疏矩陣非常有優勢。所以比較下來選擇鏈表表示稀疏矩陣。

如果說鏈表的插入，刪除比數組方便，所以矩陣都應該用鏈表表示的話我個人覺得是欠妥的，數據量超過50%以上的矩陣，其實用數組可能更好。明白什麼情況下用什麼數據結構我覺得才是你需要學習的，原始數據結構的優劣勢並不能作為直接判斷標準。

大家說了鏈表的很多優點，下面我從體系結構角度來說一下鏈表的缺點。

鏈表以O(1)複雜度插入和刪除的，但是在你往更高層看一看，有些場景下這根本不重要，為什麼不重要？因為在你插入和刪除之前，你首先要找到插入或刪除的位置，我們假設是線性搜索，相對於數組，鏈表找到那個插入位置的速度要比數組慢很多很多。

也許你會疑惑，用線性搜索的話，數組和鏈表都是O(n)的複雜度來找到插入的位置，為什麼鏈表會慢呢？在理論上可能是一樣塊的，但在現實中不是這樣的。原因是因為鏈表不是cache friendly的。你在訪問線性訪問數組的時候，因為局部性原理，系統會把之後連續的內存都讀過來，所以你之後訪問數組元素可能都在 L1 cache 裡面，但鏈表不是這樣的，誰都不知道它的next指針指到哪塊內存，導致訪問每個節點都對應一次memory而不是cache的訪問。

數組的缺點也是非常明顯的，不能動態擴容，一次擴容需要移動大量的元素等等。所以應分清楚場合使用數組或者鏈表。

如果你的應用場景是插入/刪除很少，查詢非常多，用數組；

如果你的應用場景是插入/刪除頻繁，查詢少，用鏈表。另外，作為一種優化，可以做個節點池。

附：Bjarne Stroustrup大神講的一段視頻，Why you should avoid Linked Lists

https://www.youtube.com/watch?v=YQs6IC-vgmo

樓主可以試著在數組中間（不是頭和尾插入新元素看看），然後就知道list這種東西是什麼時候該用的了

如果你需要在O(1)時間內查找元素，並且數組的大小是固定的話，vector，array，動態數組之類的數據結構肯定非常好

但如果你要頻繁插入刪除元素的話，list就比較合適了。。

根據STL或者你自己實現的方式不同，選擇也是不同的。

不知道哪本書上說過，查找時間，實現的複雜度，和內存的連續性是不可兼得的，你必須要有所取捨。。。

數組（非動態）對比鏈表：

數組簡單易用，在實現上使用的是連續的內存空間。得益於現代處理器的緩存機制，其訪問效率很高。數組的缺點是大小固定，一經聲明就要佔用整塊內存空間。如果聲明的數組過大，系統可能沒有足夠的連續內存空間分配給它。而如果聲明的數組過小，則可能出現不夠用的情況。這時只能再聲明一個更大的數組，然後把原數組拷貝進去，非常費時。

鏈表最大的特點是大小動態可調，其大小與已經而不是計劃存儲的元素個數成正比。在確定了操作點之後，插入和刪除的操作耗時是固定的。但是使用鏈表也要為其動態特性付出代價，例如每個元素都需要消耗額外的存儲空間去存儲一份指向下一個元素的指針類數據。

鏈表與數組的各種操作複雜度如下所示：

操作 ------------------- 鏈表 ---- 數組

查找 -------------------- O(n) ---- O(1)

在頭部插入/刪除 ------ O(1) ---- O(n)

在尾部插入/刪除 ------ O(n) ---- O(1)

在中間插入/刪除 ------ O(n) ---- O(n)

額外的存儲空間 ------- O(n) ---- 0

注意雖然表面看起來複雜度都是 O(n)，但是鏈表和數組在插入和刪除時進行的是完全不同的操作。鏈表的主要耗時操作是歷遍查找，刪除和插入操作本身的複雜度是O(1)。數組查找很快，主要耗時的操作是拷貝覆蓋。因為除了目標元素在尾部的特殊情況，數組進行插入和刪除時需要對操作點之後的所有元素進行前後移位操作，只能通過拷貝和覆蓋的方法進行。

from "Data Structures and Algorithms Made Easy"

關於數據結構與 ADT:

Linked-list 中的 linked 描述的仍然是數據的結構而不是實現的手段。一般意義上的實現即 implementation 是跟具體的編程語言掛鉤的。另外計算機科學中一般說 Abstract data type (ADT) 而不是 Abstract data structure。ADT 是從用戶的角度出發，關心的重點既包括數據的定義也包括數據的使用方法。而數據結構是從設計者的角度出發，關心的重點是數據的組織和存儲方式。

單論鏈表的組織和存儲方法，這時鏈表的概念就是數據結構。如果再加上鏈表的創建、歷遍、刪除、插入等操作，這時鏈表的概念就是 ADT。而用某一種編程語言實現了鏈表的 ADT，這叫做鏈表的實現。

題主可以試著在數組中（非頭尾）刪除或插入一個元素，可能就明白了。

說到底還是題主連鏈表是什麼都不清楚，就在這開始討論，沒有人規定鏈表就一定使用結構體鏈在一起的才是鏈表