無論學習任何語言，我們一定都使用過 陣列 Array。他是程式語言中最常見的存在之一。也是一個最基礎的數據結構。但我們真的了解過他的設計精髓嗎？讓我們一起來看看。
如果你有任何問題，可以透過 Email 聯絡我 support@sd0.tech
如果你想了解更多關於技術、面試與生活，歡迎到 SD0 Tech 參觀！
本文章同步更新至 Medium
最近開始審視自己所學的基礎，把這些想法分享給大家。
定義
首先，我們需要先了解陣列 Array 的定義。
在計算機科學中，陣列資料結構（英語：array data structure），簡稱數組（英語：Array），是由相同類型的元素（element）的集合所組成的資料結構，分配一塊連續的內存來存儲。利用元素的索引（index）可以計算出該元素對應的儲存地址。— Wiki 維基百科
從 Wiki 維基百科我們可以了解陣列有幾個特性：
- 相同類型的元素，比如
IntString等 - 分配一塊連續的內存
- 利用索引（index）進行訪問
相同類型的元素，我想大家應該沒什麼特別的問題。聰明的你可能想到了，那泛型（Generic）算是相同的元素嗎？這題很有趣，我們先留到之後探討。
我們先來聊聊分配一塊連續的內存與利用索引（index）進行訪問
一塊連續的內存與利用索引（index）進行訪問
不知道你有沒有好奇過，為什麼陣列總是以 0 作為起始？這樣不是很反直覺嗎。你可能會想，電腦本來就是從 0 開始的工程。不過，今天我想以另外一個角度的思考分享給你。
當分配一塊連續的內存時，我們到底在指什麼？舉個例子。
假設我們宣告 var digitCounts = Array(repeating: 0, count: 3) ，於是我們可以得到一組陣列 [0, 0, 0] 我們假設電腦分配的內存空間是 1000 - 1015 ，代表陣列的開始位置為 1000 ，即 base_address = 1000 。
那問題來了，如果我們要訪問陣列中的某個元素，電腦會如何處理他呢？我們理解，電腦會有一套尋址公式，來尋找到我們要訪問的對象。
我們要訪問的對象[i] 的內存地址 = 陣列起始位置內存地址 + i x 資料型別大小
再公式化一點就是：
a[i]’s address = base’s address + i * data type’s size
在我們的例子中，Int 的 Size 是 4byte（這邊假設是 Int32 ），所以如果 i = 2 他在內存中的位置就是：
1000 + 2 x 4 = 1008 - 1011
所以對電腦而言，一塊連續的內存與利用索引（index）進行訪問的基礎原理來自於內存記憶體的尋址方式。或者說是一個相輔相成的設計原理。
題外話，如果我們希望陣列從 1 開始，那我們的尋址方式會有什麼改變？應該會變成：
a[i]’s address = base’s address + (i - 1) * data type’s size
最直觀上的說，對於電腦 CPU 來說，就是多了一個減法指令，對於底層核心性能來說，可能是無法被接受的。
陣列 Array訪問的時間複雜度？
通過前面的描述，我們可以理解到陣列可以透過 a[2] 這種方式進行隨機訪問。訪問的時間複雜度為 O(1) 。這邊要特別注意一點，千萬別把訪問與搜索混為一談，如果要對於陣列進行搜索指定數值，最快的時間複雜度也是 O(logn) （因為基於二分查找）。所以如果在面試中，最好表達清楚，陣列 Array 支持根據 index 隨機訪問，時間複雜度為 O(1)。
接下來我們來聊聊陣列 Array 的新增與刪除元素。
陣列 Array 的新增與刪除元素
我們知道陣列 Array 通常支持新增與刪除元素，在 Swift 中我們會使用 arr.append(item) 操作新增一個元素，arr.remove(at: 2) 表示刪除 index = 2 的元素。
那我們使用新增的時間複雜度為何？很直觀地想，我們將一個元素新增到陣列末尾，那他的時間複雜度應該是 O(1) 吧？沒錯，在陣列 Array 容量足夠的情況下，加入到陣列 Array 末尾，時間複雜度為 O(1) ，但如果陣列空間已經滿了呢？
這邊要牽涉到另外一個問題，陣列 Array 的擴容。
陣列 Array 的擴容
在 Swift 中，需要進行擴容時，會以原有的基礎進行兩倍擴容。比如原本陣列 Array 數量為 2 當要加入第 3 個元素時，Swift 會開啟新的陣列，長度為 4 ，並且將舊資料複製過去，再加入新元素。雖然這麼做會浪費一點空間，但是會節省一些擴容的性能消耗。
綜上所述，我們知道 陣列 Array 的新增元素並不是所有時刻都是 O(1) 的，取決於是否需要擴容。了解了這一點，對於我們撰寫程式一定會更加有概念以及注意。
陣列 Array 的刪除元素
如果我們要刪除陣列 Array 中的元素，電腦需要將刪除指定 index 之後的數據進行搬移。簡單來說，要刪除 index = 2 的元素時，電腦需要將 2 之後的數據都進行搬移，以確保內存記憶體的連續性。所以刪除數據的時間複雜度是 O(n) 的。我們可以試想最好的情況，就是後面沒有數據，那在這個情況下，就不用進行搬移，時間複雜度就是 O(1) 。
不過，在實際上，因為每次進行搬移會消耗太多性能。當遇到一些連續刪除操作時，為了避免連續搬移帶來的性能損耗，通常會先進行標記刪除，當真的沒有更多的空間時，再一次做刪除並且搬移。
比如現在有一個陣列 [a, b, c, d, e] ，我們今天連續執行刪除 index = 0 、index = 1 ，此時在內存上不一定真的已經刪除，有可能是標記刪除，當我們進行 append 操作時，因為容量已滿，才會將標記刪除的項目刪除。
陣列的插入元素
試著想一個情況，當我們要插入一個元素時，電腦會如何運行？當然，如果這個插入操作是插入到陣列 Array 的末尾，那就相當於新增操作，時間複雜度為 O(1)
如果要將元素插入到第 K 個位置呢？
此時，電腦需要將 K 個位置之後的元素都往後挪，然後再把元素放置到這個位置。那時間複雜度就是 O(n) 的。
那我們可以避免這種搬移帶來的性能損失嗎？答案是可以的。
如果陣列 Array 不需要排序，我們可以將第 K 位原有的數據直接移動到陣列 Array 的末尾。然後將第 K 位的數據直接取代成要插入的數據，在這種情況下，時間複雜度就是 O(1)
Out of Index
剛開始接觸程式的朋友，一定多多少少都看過這個錯誤 Out of Index ，他的意思是你的訪問越界了。我們在撰寫程式，甚至在生活中，一定要注意邊界。邊界可以幫助我們避免很多試錯的成本。在計算機科學中，也有很多系統漏洞因為越界而產生的。
總結
在準備新工作面試的這段時間裡，我重新認識了陣列 Array。我理解到了解原理是很重要的，他不但會讓你知道這些東西的工作方式，也了解到邊界在哪裡，我們就可以在邊界裡發揮創意與成果。今天我們就聊到這裡，感謝你的閱讀，我們下次見！