向量和鏈接列表之間的區別ADT

Question

有人可以向我解釋在c編程語言上下文中向量和鏈接列表ADT之間的區別。

謝謝。

Answer 1

那麼，在C中，沒有像「C++ std庫」中那樣的「vector」和「list」數據類型可以直接使用。但就「抽象數據類型」而言，矢量通常被認爲代表連續存儲，並且鏈接列表被認爲是由連接在一起的單個單元表示的。向量提供快速的恆定時間隨機訪問讀取和寫入操作，但插入和刪除向量元素需要線性時間。列表具有線性查找性能，用於查找要讀取和寫入的元素，但給定元素位置後，會有恆定的時間插入和刪除。您也可以在常量時間內將項目添加到列表的開始和結尾（如果ADT實現緩存列表中最後一個元素的位置）。

Answer 2

基本上，一個向量駐留在連續的內存中。鏈表包含指向前一個和下一個結構的指針。隨機訪問的矢量速度更快，鏈表更適合成長。

http://www.codeguru.com/forum/archive/index.php/t-309352.html

Answer 3

vector是一個動態數組。內存中的元素相鄰。鏈接列表中的元素不相鄰。

Answer 4

一個向量通常作爲一個連續的內存塊被實現爲一個數組。而列表可以分佈在內存中，因爲每個元素持有指向一個或多個其他元素的指針（可以雙重鏈接）。這爲向量提供了訪問速度優勢，但列出了插入/刪除優勢。