1.   重點回顧

• 數(shù)組和鏈表是兩種基本的數(shù)據結構，分別代表數(shù)據在計算機內存中的兩種存儲方式：連續(xù)空間存儲和離散空間存儲。兩者的特點呈現(xiàn)出互補的特性。
• 數(shù)組支持隨機訪問、占用內存較少；但插入和刪除元素效率低，且初始化后長度不可變。
• 鏈表通過更改引用（指針）實現(xiàn)高效的節(jié)點插入與刪除，且可以靈活調整長度；但節(jié)點訪問效率低、占用內存較多。常見的鏈表類型包括單向鏈表、循環(huán)鏈表、雙向鏈表。
• 動態(tài)數(shù)組，又稱列表，是基于數(shù)組實現(xiàn)的一種數(shù)據結構。它保留了數(shù)組的優(yōu)勢，同時可以靈活調整長度。列表的出現(xiàn)極大地提高了數(shù)組的易用性，但可能導致部分內存空間浪費。

2.   Q & A

數(shù)組存儲在棧上和存儲在堆上，對時間效率和空間效率是否有影響？

存儲在棧上和堆上的數(shù)組都被存儲在連續(xù)內存空間內，數(shù)據操作效率是基本一致的。然而，棧和堆具有各自的特點，從而導致以下不同點。

1. 分配和釋放效率：棧是一塊較小的內存，分配由編譯器自動完成；而堆內存相對更大，可以在代碼中動態(tài)分配，更容易碎片化。因此，堆上的分配和釋放操作通常比棧上的慢。
2. 大小限制：棧內存相對較小，堆的大小一般受限于可用內存。因此堆更加適合存儲大型數(shù)組。
3. 靈活性：棧上的數(shù)組的大小需要在編譯時確定，而堆上的數(shù)組的大小可以在運行時動態(tài)確定。

為什么數(shù)組要求相同類型的元素，而在鏈表中卻沒有強調同類型呢？

鏈表由結點組成，結點之間通過引用（指針）連接，各個結點可以存儲不同類型的數(shù)據，例如 int、double、string、object 等。

相對地，數(shù)組元素則必須是相同類型的，這樣才能通過計算偏移量來獲取對應元素位置。例如，如果數(shù)組同時包含 int 和 long 兩種類型，單個元素分別占用 4 bytes 和 8 bytes ，那么此時就不能用以下公式計算偏移量了，因為數(shù)組中包含了兩種長度的元素。

# 元素內存地址 = 數(shù)組內存地址 + 元素長度 * 元素索引

刪除節(jié)點后，是否需要把 ?P.next ?設為 None 呢？

不修改 ?P.next? 也可以。從該鏈表的角度看，從頭結點遍歷到尾結點已經遇不到 ?P? 了。這意味著結點 ?P? 已經從鏈表中刪除了，此時結點 ?P? 指向哪里都不會對這條鏈表產生影響了。

從垃圾回收的角度看，對于 Java、Python、Go 等擁有自動垃圾回收的語言來說，節(jié)點 ?P? 是否被回收取決于是否有仍存在指向它的引用，而不是 ?P.next? 的值。在 C 和 C++ 等語言中，我們需要手動釋放節(jié)點內存。

在鏈表中插入和刪除操作的時間復雜度是 O(1) 。但是增刪之前都需要 O(n) 查找元素，那為什么時間復雜度不是 O(n) 呢？

如果是先查找元素、再刪除元素，確實是 O(n) 。然而，鏈表的 O(1) 增刪的優(yōu)勢可以在其他應用上得到體現(xiàn)。例如，雙向隊列適合使用鏈表實現(xiàn)，我們維護一個指針變量始終指向頭結點、尾結點，每次插入與刪除操作都是 O(1) 。

圖片“鏈表定義與存儲方式”中，淺藍色的存儲結點指針是占用一塊內存地址嗎？還是和結點值各占一半呢？

文中的示意圖只是定性表示，定量表示需要根據具體情況進行分析。

• 不同類型的結點值占用的空間是不同的，比如 int、long、double 和實例對象等。
• 指針變量占用的內存空間大小根據所使用的操作系統(tǒng)及編譯環(huán)境而定，大多為 8 字節(jié)或 4 字節(jié)。

在列表末尾添加元素是否時時刻刻都為 O(1) ？

如果添加元素時超出列表長度，則需要先擴容列表再添加。系統(tǒng)會申請一塊新的內存，并將原列表的所有元素搬運過去，這時候時間復雜度就會是 O(n) 。

“列表的出現(xiàn)大大提升了數(shù)組的實用性，但副作用是會造成部分內存空間浪費”，這里的空間浪費是指額外增加的變量如容量、長度、擴容倍數(shù)所占的內存嗎？

這里的空間浪費主要有兩方面含義：一方面，列表都會設定一個初始長度，我們不一定需要用這么多。另一方面，為了防止頻繁擴容，擴容一般都會乘以一個系數(shù)，比如 ×1.5 。這樣一來，也會出現(xiàn)很多空位，我們通常不能完全填滿它們。

在 Python 中初始化? n = [1, 2, 3] ?后，這 3 個元素的地址是相連的，但是初始化 ?m = [2, 1, 3]? 會發(fā)現(xiàn)它們每個元素的 id 并不是連續(xù)的，而是分別跟 ?n? 中的相同。這些元素地址不連續(xù)，那么 ?m? 還是數(shù)組嗎？

假如把列表元素換成鏈表節(jié)點 ?n = [n1, n2, n3, n4, n5] ?，通常情況下這五個節(jié)點對象也是被分散存儲在內存各處的。然而，給定一個列表索引，我們仍然可以在 O(1) 時間內獲取到節(jié)點內存地址，從而訪問到對應的節(jié)點。這是因為數(shù)組中存儲的是節(jié)點的引用，而非節(jié)點本身。

與許多語言不同的是，在 Python 中數(shù)字也被包裝為對象，列表中存儲的不是數(shù)字本身，而是對數(shù)字的引用。因此，我們會發(fā)現(xiàn)兩個數(shù)組中的相同數(shù)字擁有同一個 id ，并且這些數(shù)字的內存地址是無須連續(xù)的。

C++ STL 里面的 std::list 已經實現(xiàn)了雙向鏈表，但好像一些算法的書上都不怎么直接用這個，是不是有什么局限性呢?

一方面，我們往往更青睞使用數(shù)組實現(xiàn)算法，而只有在必要時才使用鏈表，主要有兩個原因。

• 空間開銷：由于每個元素需要兩個額外的指針（一個用于前一個元素，一個用于后一個元素），所以 ?std::list? 通常比 ?std::vector? 更占用空間。
• 緩存不友好：由于數(shù)據不是連續(xù)存放的，std::list 對緩存的利用率較低。一般情況下，std::vector 的性能會更好。

另一方面，必要使用鏈表的情況主要是二叉樹和圖。棧和隊列往往會使用編程語言提供的 ?stack? 和 ?queue? ，而非鏈表。