文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

如何實現隨機訪問

數組是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。

線性表

線性表的數據最多只有前和后兩個方向。數組、棧、隊列、鏈表都是線性表。
非線性表：樹、圖、堆。

連續的內存空間

$a[i]\_address=base\_address+i?data\_type\_size$,data_type_size表示數組中每個元素的大小。
如果數組下標從1開始，那么在查找$a[i]\_address=base\_address+(i?1)?data\_type\_size$會多一次減法操作。這可能是大多數語言數組下標從0開始的原因。

與鏈表的區別

數組支持隨機訪問，復雜度O(1)。鏈表適合插入刪除。

低效地插入和刪除

插入：如果某個位置a[i]已經被占用了，就需要將i到最后一個元素拷貝到i+1到count位置，然后a[i]=val。平均時間復雜度O(n)。
改進策略：大多數時候我們不需要追求順序性，那么我們可以把a[i]復制到數組末尾，將 當前元素賦值給a[i]。例如數組a[10]，已經存入元素：1，2，3，4，5。現在想插入a[2]=10，那么插入完成后數組變為：1，2，10，4，5，3。

刪除：因為內存塊是連續的，當刪除i位的元素后，從i+1到count的元素需要向前遷移。這樣平均復雜度也是O(n)。
刪除的改進策略可以是：刪除的位置先做標記不做遷移，等空間不夠的時候再做遷移。這就是Java虛擬的標記清除算法。

警惕數組越界

數組越界是通常需要處理的問題。在C中數組越界可能會產生意想不到的結果。

容器能否完全替代數組

在某些場合還是用數組不會用容器。例如：
1 數組可以存儲基本數據類型，速度上更快。在已知數組大小，并且操作簡單的情況下數組是個更好的選擇。
2 多維數組一般用數組表示。a[][] 這樣的表示比List<List> 這樣的結構更容易接受。

總結

以上是生活随笔為你收集整理的数据结构一—— 数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。