C++中的動態數組VS VS鏈接列表

Question

當我們有動態數組列表時，爲什麼我們需要鏈接列表？

我研究過靜態列表和鏈表。我有動態數組列表的知識。但我無法找出確切的區別 任何人請幫我回答這個問題

Answer 1

動態數組是根據內容數量調整自身大小的數組。

優勢：

• 訪問和分配由索引是非常快的O（1）過程中，由於內部索引訪問只是[address of first member] + [offset]。追加對象（在數組末尾插入）相對較快的攤銷O（1）。與刪除數組末尾的對象相同的性​​能特徵。注意：在數組末尾附近添加和移除對象也稱爲推送和彈出。

缺點：

• 插入或者在一個動態數組的隨機位置移除對象是很慢的O（N/2），因爲它必須轉移（平均）的一半數組每次。特別差的是在陣列開始附近插入和移除，因爲它必須複製整個陣列。

• 當插入或去除需要調整大小

• 有一個位的未使用的空間中，由於動態數組實現通常比需要分配更多的存儲器

  不可預知的性能（因爲調整大小是一個非常緩慢的操作）

鏈接列表是一個對象，它的一般結構爲[head, [tail]],head是數據，而tail是另一個鏈接列表。鏈表有多種版本：單數LL，雙LL，圓LL等。

優勢：

• 快速O（1）的插入和移除在列表中的任何位置，如插入在鏈表僅打破列表，插入和修復它回到一起（沒有需要複製尾部）

• 鏈表是一個持久的數據結構，很難用短句解釋，參見：wiki-link。這個優勢允許尾部共享兩個鏈表之間。尾部共享可以很容易地將鏈接列表用作寫時複製數據結構。

缺點：

• 慢O（n）的索引訪問（隨機存取），因爲通過索引訪問鏈表意味着你必須在列表上遞歸循環。

• 不好的地方，用於鏈表的內存散亂一團。與在內存中使用連續地址的數組相反。從處理器高速緩存陣列（略）的好處，因爲他們都是互相靠近

其他：

• 由於鏈表的性質，你必須遞歸認爲。不習慣遞歸函數的程序員在爲鏈表編寫算法時可能會遇到一些困難（或者更糟糕的是他們可能會嘗試使用索引）。

簡而言之，當您要使用需要隨機訪問的算法時，請忘記鏈接列表。當你想使用需要大量插入和移除的算法時，忘記數組。

這是從這個question

最好的答案我被這個答案相信服用。

Answer 2

矢量又名動態數組：像普通數組一樣。連續的存儲單元用於存儲矢量。無論何時您需要分配更多內存，並且內存在當前位置不可用，整個陣列都會被複制到另一個位置，並分配額外的內存。

列表：在每個元素中維護一個指針，並且該指針指向下一個元素。

What are the complexity guarantees of the standard containers? 看看這個鏈接瞭解更多信息。