陣列與鏈結串列的差異：讀取、插入與刪除、記憶體排列、快取與時間複雜度比較
陣列是把相同型別的元素在記憶體上毫無間隙地連續排列，能從元素編號（索引）計算出位置，以固定的時間讀寫任一元素的資料結構。鏈結串列是每個元素都有值與指向下一個元素位置的指標，沿著指標串接起來的資料結構，元素可以放在記憶體中彼此分離的位置。陣列讀取快，但在中間插入或刪除時，必須移動後面的元素。鏈結串列只要知道位置，只需改接指標就能插入或刪除，但要讀第i個元素，必須從開頭依序走訪。常以編號讀取時用陣列，常在已知位置插入或刪除時用鏈結串列，是基本的使用原則。
| 項目 | 陣列 | 鏈結串列 |
|---|---|---|
| 記憶體上的排列方式 | 元素在連續的區域中毫無間隙地排列 | 元素放在分散的位置，以指標串接 |
| 讀取第i個元素 | O(1)。可用「開頭位址 + i × 元素大小」計算位置 | O(n)。從開頭沿指標走i次 |
| 搜尋值 | 未排序時為O(n)的線性搜尋。已排序時以二分搜尋為O(log n) | 即使已排序也是O(n)。無法一次移到中間的元素，因此不能使用二分搜尋 |
| 在中間插入、刪除 | O(n)。把後面的元素逐一移動 | 知道插入位置（前一個元素）時為O(1)。只需改接指標 |
| 在尾端新增 | 有空位時為O(1)。可變長度陣列以每次加倍容量的方式時，偶爾需要複製全部，但平均為O(1)（攤銷） | 若保有指向最後一個元素的指標，則為O(1) |
| 改變大小 | 固定長度的陣列在建立時就決定大小。要擴大時，需配置新的區域並複製 | 每個元素各自配置空間，因此只需增加需要的量 |
| 使用的記憶體 | 只需元素本身的空間（可變長度陣列會保留預備的容量） | 每個元素都需要額外的指標空間（雙向串列為2個） |
| 快取是否容易生效 | 容易。元素連續排列，依序讀取時快取與預取都能良好運作 | 不容易。元素容易分散，即使同樣是O(n)的走訪，也可能比陣列慢很多 |
| 主要用途 | 以索引讀寫的表、矩陣與影像、排序或二分搜尋的對象、堆疊與佇列的實作 | 插入與刪除頻繁的序列、雜湊表的鏈結法、可用空間的管理 |
數值為具代表性的大致參考值，會因世代或產品而異。