1.   重點(diǎn)回顧

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

2.   Q & A

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

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

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

為什么數(shù)組要求相同類型的元素，而在鏈表中卻沒(méi)有強(qiáng)調(diào)同類型呢？

鏈表由結(jié)點(diǎn)組成，結(jié)點(diǎn)之間通過(guò)引用（指針）連接，各個(gè)結(jié)點(diǎn)可以存儲(chǔ)不同類型的數(shù)據(jù)，例如 int、double、string、object 等。

相對(duì)地，數(shù)組元素則必須是相同類型的，這樣才能通過(guò)計(jì)算偏移量來(lái)獲取對(duì)應(yīng)元素位置。例如，如果數(shù)組同時(shí)包含 int 和 long 兩種類型，單個(gè)元素分別占用 4 bytes 和 8 bytes ，那么此時(shí)就不能用以下公式計(jì)算偏移量了，因?yàn)閿?shù)組中包含了兩種長(zhǎng)度的元素。

# 元素內(nèi)存地址 = 數(shù)組內(nèi)存地址 + 元素長(zhǎng)度 * 元素索引

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

不修改 ?P.next? 也可以。從該鏈表的角度看，從頭結(jié)點(diǎn)遍歷到尾結(jié)點(diǎn)已經(jīng)遇不到 ?P? 了。這意味著結(jié)點(diǎn) ?P? 已經(jīng)從鏈表中刪除了，此時(shí)結(jié)點(diǎn) ?P? 指向哪里都不會(huì)對(duì)這條鏈表產(chǎn)生影響了。

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

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

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

圖片“鏈表定義與存儲(chǔ)方式”中，淺藍(lán)色的存儲(chǔ)結(jié)點(diǎn)指針是占用一塊內(nèi)存地址嗎？還是和結(jié)點(diǎn)值各占一半呢？

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

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

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

如果添加元素時(shí)超出列表長(zhǎng)度，則需要先擴(kuò)容列表再添加。系統(tǒng)會(huì)申請(qǐng)一塊新的內(nèi)存，并將原列表的所有元素搬運(yùn)過(guò)去，這時(shí)候時(shí)間復(fù)雜度就會(huì)是 O(n) 。

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

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

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

假如把列表元素?fù)Q成鏈表節(jié)點(diǎn) ?n = [n1, n2, n3, n4, n5] ?，通常情況下這五個(gè)節(jié)點(diǎn)對(duì)象也是被分散存儲(chǔ)在內(nèi)存各處的。然而，給定一個(gè)列表索引，我們?nèi)匀豢梢栽?nbsp;O(1) 時(shí)間內(nèi)獲取到節(jié)點(diǎn)內(nèi)存地址，從而訪問(wèn)到對(duì)應(yīng)的節(jié)點(diǎn)。這是因?yàn)閿?shù)組中存儲(chǔ)的是節(jié)點(diǎn)的引用，而非節(jié)點(diǎn)本身。

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

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

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

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

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