iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
Software Development

少女人妻在廚房裡想不通的演算法系列 第 7

【在廚房想30天的演算法】Day 07 資料結構:陣列 Array

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


陣列 (Array)

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

陣列的定義與特性

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

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

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

yVgHEh1

常見的基本操作

插入資料元素

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

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

R7dlqGe

0JqoqV9

然後就噹啷~成功了

4Pzcy15

刪除資料元素

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

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

znCLruS

cZB0BvS

關於陣列的時間複雜度

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

參考資料:

JavaScript 學演算法(四)- 陣列 Array


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


上一篇
【在廚房想30天的演算法】Day 06 資料結構:連結串列 Linked List
下一篇
【在廚房想30天的演算法】Day 08 資料結構:堆疊 Stack
系列文
少女人妻在廚房裡想不通的演算法30

尚未有邦友留言

立即登入留言