Aloha～又是我少女人妻 Uerica ！ 中秋節過後就是秋天了，秋高氣爽是最適合旅遊的日子了，可惜連假已過而且還要寫鐵人賽文章呢～哈哈哈哈哈哈哈5555...

陣列 (Array)

今天要來聊聊大家耳熟能詳的陣列了！一般的程式語言都會內建陣列的資料型別 (type)，除了少部分語言是由雜湊表、連結串列、搜尋樹等來實現，像 Javascrpt 就是使用類似雜湊表資料結構的方式。

陣列的定義與特性

陣列與連結串列相同，也是屬於線性資料結構，但陣列在宣告時就得定義記憶體空間的大小 (陣列長度)，且是連續的儲存在記憶體空間，而陣列內所儲存的資料都需是相同型態。

而陣列在插入與刪除資料元素較為費時，因是連續的儲存在記憶體空間，不像連結串列僅改變指標指向的節點即可，陣列在插入與刪除資料元素都得往後或往前移動所有元素。但在存取時因是連續性的資料，記憶體可計算出內容的索引 (index) 位置，所以能直接做存取，又稱隨機存取 (Random Access)。

• 優點
  • 宣告時就得定義陣列長度，若是確定長度且不會變的資料，因只存資料元素，會比連結串列來得省空間。
  • 在記憶體中是連續儲存的緣故，可用索引做隨機存取，且存取效能較快。
• 缺點
  • 宣告時得定義陣列長度，若無法確定或時常插入、刪除元素，會造成記憶體佔用空間過多或過少的可能。
  • 因是連續儲存，插入或刪除資料元素較為費時。

常見的基本操作

插入資料元素

若需要插入新的資料元素，要先確保陣列有足夠長度，並由最後一個資料元素開始向後移動，直到需插入新資料元素的位置空出來。

如圖示，今天要插入 data New 在data A與data B之間，首先須先確認陣列長度是否足夠，再由最後方開始往後移動，直到空出欲插入的位置

然後就噹啷～成功了

刪除資料元素

若要刪除陣列中的資料元素，在取出欲刪除的資料元素後，後方的資料元素需要一個個全部向前移動，直到所有資料元素都接續在一起。

現在想將 data B 的資料刪除，要先將 data B 取出，之後讓後方的 data C 往前接續

關於陣列的時間複雜度

由於陣列屬於隨機存取，所以在存取任一資料元素時，時間複雜度為 O(1)。若需要插入或刪除資料元素，因要一個個調整，故時間複雜度為 O(n)。

參考資料：

JavaScript 學演算法（四）- 陣列 Array

好搭！今天就先到這邊啦！感謝閱讀～今年連假跟去年連假一樣都是在寫鐵人賽文章，參賽的各位都是防疫大使呢！呵呵呵呵呵...明天見啦掰掰～