跳轉至

4.5   小結

1.   重點回顧

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

2.   Q & A

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

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

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

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

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

  • 不同型別的節點值佔用的空間是不同的，比如 int、long、double 和例項物件等。
  • 指標變數佔用的記憶體空間大小根據所使用的作業系統及編譯環境而定，大多為 8 位元組或 4 位元組。

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] 。