4.5 小結¶

陣列和鏈結串列是兩種基本的資料結構，分別代表資料在計算機記憶體中的兩種儲存方式：連續空間儲存和分散空間儲存。兩者的特點呈現出互補的特性。
陣列支持隨機訪問、佔用記憶體較少；但插入和刪除元素效率低，且初始化後長度不可變。
鏈結串列透過更改引用（指標）實現高效的節點插入與刪除，且可以靈活調整長度；但節點訪問效率低、佔用記憶體較多。常見的鏈結串列型別包括單向鏈結串列、環形鏈結串列、雙向鏈結串列。
串列是一種支持增刪查改的元素有序集合，通常基於動態陣列實現。它保留了陣列的優勢，同時可以靈活調整長度。
串列的出現大幅提高了陣列的實用性，但可能導致部分記憶體空間浪費。
程式執行時，資料主要儲存在記憶體中。陣列可提供更高的記憶體空間效率，而鏈結串列則在記憶體使用上更加靈活。
快取透過快取行、預取機制以及空間區域性和時間區域性等資料載入機制，為 CPU 提供快速資料訪問，顯著提升程式的執行效率。
由於陣列具有更高的快取命中率，因此它通常比鏈結串列更高效。在選擇資料結構時，應根據具體需求和場景做出恰當選擇。

Q：陣列儲存在堆疊上和儲存在堆積上，對時間效率和空間效率是否有影響？

儲存在堆疊上和堆積上的陣列都被儲存在連續記憶體空間內，資料操作效率基本一致。然而，堆疊和堆積具有各自的特點，從而導致以下不同點。

分配和釋放效率：堆疊是一塊較小的記憶體，分配由編譯器自動完成；而堆積記憶體相對更大，可以在程式碼中動態分配，更容易碎片化。因此，堆積上的分配和釋放操作通常比堆疊上的慢。
大小限制：堆疊記憶體相對較小，堆積的大小一般受限於可用記憶體。因此堆積更加適合儲存大型陣列。
靈活性：堆疊上的陣列的大小需要在編譯時確定，而堆積上的陣列的大小可以在執行時動態確定。

Q：為什麼陣列要求相同型別的元素，而在鏈結串列中卻沒有強調相同型別呢？

鏈結串列由節點組成，節點之間透過引用（指標）連線，各個節點可以儲存不同型別的資料，例如 int、double、string、object 等。

相對地，陣列元素則必須是相同型別的，這樣才能透過計算偏移量來獲取對應元素位置。例如，陣列同時包含 int 和 long 兩種型別，單個元素分別佔用 4 位元組和 8 位元組，此時就不能用以下公式計算偏移量了，因為陣列中包含了兩種“元素長度”。

# 元素記憶體位址 = 陣列記憶體位址（首元素記憶體位址） + 元素長度 * 元素索引

Q：刪除節點 P 後，是否需要把 P.next 設為 None 呢？

不修改 P.next 也可以。從該鏈結串列的角度看，從頭節點走訪到尾節點已經不會遇到 P 了。這意味著節點 P 已經從鏈結串列中刪除了，此時節點 P 指向哪裡都不會對該鏈結串列產生影響。

從資料結構與演算法（做題）的角度看，不斷開沒有關係，只要保證程式的邏輯是正確的就行。從標準庫的角度看，斷開更加安全、邏輯更加清晰。如果不斷開，假設被刪除節點未被正常回收，那麼它會影響後繼節點的記憶體回收。

Q：在鏈結串列中插入和刪除操作的時間複雜度是 \(O(1)\) 。但是增刪之前都需要 \(O(n)\) 的時間查詢元素，那為什麼時間複雜度不是 \(O(n)\) 呢？

如果是先查詢元素、再刪除元素，時間複雜度確實是 \(O(n)\) 。然而，鏈結串列的 \(O(1)\) 增刪的優勢可以在其他應用上得到體現。例如，雙向佇列適合使用鏈結串列實現，我們維護一個指標變數始終指向頭節點、尾節點，每次插入與刪除操作都是 \(O(1)\) 。

Q：圖“鏈結串列定義與儲存方式”中，淺藍色的儲存節點指標是佔用一塊記憶體位址嗎？還是和節點值各佔一半呢？

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

Q：在串列末尾新增元素是否時時刻刻都為 \(O(1)\) ？

如果新增元素時超出串列長度，則需要先擴容串列再新增。系統會申請一塊新的記憶體，並將原串列的所有元素搬運過去，這時候時間複雜度就會是 \(O(n)\) 。

Q：“串列的出現極大地提高了陣列的實用性，但可能導致部分記憶體空間浪費”，這裡的空間浪費是指額外增加的變數如容量、長度、擴容倍數所佔的記憶體嗎？

這裡的空間浪費主要有兩方面含義：一方面，串列都會設定一個初始長度，我們不一定需要用這麼多；另一方面，為了防止頻繁擴容，擴容一般會乘以一個係數，比如 \(\times 1.5\) 。這樣一來，也會出現很多空位，我們通常不能完全填滿它們。

Q：在 Python 中初始化 n = [1, 2, 3] 後，這 3 個元素的位址是相連的，但是初始化 m = [2, 1, 3] 會發現它們每個元素的 id 並不是連續的，而是分別跟 n 中的相同。這些元素的位址不連續，那麼 m 還是陣列嗎？

假如把串列元素換成鏈結串列節點 n = [n1, n2, n3, n4, n5] ，通常情況下這 5 個節點物件也分散儲存在記憶體各處。然而，給定一個串列索引，我們仍然可以在 \(O(1)\) 時間內獲取節點記憶體位址，從而訪問到對應的節點。這是因為陣列中儲存的是節點的引用，而非節點本身。

與許多語言不同，Python 中的數字也被包裝為物件，串列中儲存的不是數字本身，而是對數字的引用。因此，我們會發現兩個陣列中的相同數字擁有同一個 id ，並且這些數字的記憶體位址無須連續。

Q：C++ STL 裡面的 std::list 已經實現了雙向鏈結串列，但好像一些演算法書上不怎麼直接使用它，是不是因為有什麼侷限性呢？

一方面，我們往往更青睞使用陣列實現演算法，而只在必要時才使用鏈結串列，主要有兩個原因。

空間開銷：由於每個元素需要兩個額外的指標（一個用於前一個元素，一個用於後一個元素），所以 std::list 通常比 std::vector 更佔用空間。
快取不友好：由於資料不是連續存放的，因此 std::list 對快取的利用率較低。一般情況下，std::vector 的效能會更好。

另一方面，必要使用鏈結串列的情況主要是二元樹和圖。堆疊和佇列往往會使用程式語言提供的 stack 和 queue ，而非鏈結串列。

Q：初始化串列 res = [0] * self.size() 操作，會導致 res 的每個元素引用相同的位址嗎？

不會。但二維陣列會有這個問題，例如初始化二維串列 res = [[0]] * self.size() ，則多次引用了同一個串列 [0] 。