鏈表和陣列的區別
參考鏈接：
https://techdifferences.com/difference-between-array-and-linked-list.html
https://www.2cto.com/kf/201605/507830.html
陣列和鏈表之間的主要區別在于它們的結構，
- 陣列是基于索引（index）的資料結構，其中每個元素都與索引相關聯，
- 鏈表依賴于參考（reference），其中每個節點都由資料以及對上一個和下一個元素的參考組成，
比較
| 比較依據 | 陣列 | 鏈表 |
|---|---|---|
| 大小 | 宣告時指定 | 無需指定，在執行時變化 |
| 儲存分配 | 編譯時分配 | 運行時分配 |
| 元素順序 | 連續的 | 隨機的 |
| 訪問元素 | 使用陣列索引（下標）訪問：更快 | 從頭節點遍歷：比較慢 |
| 元素的插入和洗掉 | 相對較慢 | 更簡單、更快速、更高效 |
| 搜索 | 二分搜索（有序）或線性搜索 | 線性搜索 |
| 所需記憶體 | 少 | 多 |
陣列和鏈表之間的區別
- 陣列的大小是固定的，相比之下，鏈表是動態和靈活的，可以擴展和收縮其大小，
- 在陣列中，記憶體是在編譯時分配的，而在鏈接串列中，記憶體是在執行或運行時分配的，
- 存盤位置上，陣列邏輯上相鄰的元素在物理存盤位置上也相鄰，而鏈表不一定，
- 訪問陣列元素很快，即，如果要進入第四個元素，則必須在方括號內寫入變數名稱及其索引或位置，即，如果要訪問第四個元素，則可以直接通過索引訪問，但是，在鏈表中，必須從頭部開始，然后一直作業到第四個元素，
- 插入和洗掉時，陣列平均需要移動n/2個元素，而鏈表只需修改指標即可，
- 按序號查找時，陣列可以直接用索引進行隨機訪問，時間復雜度為O(1) ，而鏈表不支持隨機訪問，平均需要O(n)，
- 按值查找時，若陣列無序，陣列和鏈表時間復雜度均為O(N)，但是當陣列有序時，可以采用二分查找將時間復雜度降為O(logN)，
- 由于實際資料存盤在陣列的索引中，因此記憶體需求較少，相反，由于鏈表額外存盤了下一個和上一個節點的參考，因此在鏈表中需要更多的記憶體，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/445577.html
標籤：其他
上一篇：API介面測驗意義
下一篇：撰寫快取友好型程式技巧