Data Structure: Arrays

Sometimes, an array is also called a list. Array organizes elements sequentially and in order. Data stored in the memory is one after another.

有時候不同語言在操作array上，會有不同的時間複雜度或空間複雜度

JavaScript:

const example = ['a', 'b', 'c', 'd']

	JavaScript Method	Time Complexity	Space Complexity	Example Result
lookup	`example[1]`	O(1)	O(1)	`'a'`
add an element to the end of the array	`example.push('e')`	O(1)	O(1)	`['a', 'b', 'c', 'd', 'e']`
remove the last element	`example.pop()`	O(1)	O(1)	`['a', 'b', 'c']`
add an element at the beginning of the array	`example.unshift('x')`	O(n) looping the array and reassigning the indexes	O(n) looping the array and reassigning the indexes	`['x', 'a', 'b', 'c', 'd']`
remove or add an element into any place of the array	`example.splice(1, 0, 'pikachu')`	O(n) looping the array and reassigning the indexes	O(n) looping the array and reassigning the indexes	`['a', 'pikachu', 'b', 'c', 'd']`

Go:

example := []string{"a", "b", "c", "d"}

	Go Function	Time Complexity	Space Complexity	Example Result
lookup	`get := example[1]`	O(1)	O(1)	`"a"`
add an element to the end of the array	`example = append(example, "e")`	通常: O(1) / 需要擴充底層時: O(n)	通常: O(1) / 需要擴充底層時: O(n)	`["a", "b", "c", "d", "e"]`
remove the last element	`example = example[:len(example)-1]`	O(1)	O(1)	`["a", "b", "c"]`
add an element at the beginning of the array	`example = append([]string{"x"}, example...)`	O(n) 需要建立一個新的slice並複製現有的elements	O(n) 需要建立一個新的slice並複製現有的elements	`["x", "a", "b", "c", "d"]`
add an element into any place of the array	`newSlice := append(example[:1], append([]string{"pikachu"}, example[1:]...)...)`	O(n) 需要移動插入的點之後的所有elements	O(n) 需要移動插入的點之後的所有elements	`["a", "pikachu", "b", "c", "d"]`

Static Array

array的容量是固定的，每次要操作這個array時，都要符合他的大小限制，適合可預測資料量的情境。就像一個可以放六個布丁的箱子，硬要放七個布丁，就會有一個布丁放不進去

	Time Complexity	Space Complexity
lookup	O(1)	O(1)	直接以index取得指定element
push	O(1)	O(1)	如果array還有空間，增加一個element在最後
insert	O(n)	O(n)	如果array還有空間，在指定的index插入一個element，需要重新排序index
delete	O(n)	O(n)	刪除指定index的element，需要重新排序index

Dynamic Array

根據使用情境擴充array的容量，適合用在不確定資料量或需要經常變更資料量的情況，但擴充容量時可能會使影響效能

	Time Complexity	Space Complexity
lookup	O(1)	O(1)	直接以index取得指定element
append	通常: O(1)
需要擴充底層時: O(n)	通常: O(1)
需要擴充底層時: O(n)	增加一個element在最後
insert	O(n)	O(n)	在指定的index插入一個element，需要重新排序index
delete	O(n)	O(n)	刪除指定index的element，需要重新排序index

Static Array V.S. Dynamic Array

兩種資料結構各有優缺點，實際選擇需要考量運用情境和業務考量，以及所使用的開發語言的特性

	Static Array	Dynamic Array
效能	insert & delete較快，因為不用考慮擴充的情況	在需要擴充時，效能可能暫時下降，因為需要重新分配內存空間和複製現有elements
內存	內存使用量固定且可預測，適合內存有限制的情況	彈性大，較難預測內存使用量，通常會分配較多的內存空間，以因應資料量的增長
適用場景	可預測資料量、內存受限且有高度效能需求	不確定資料量或需要經常變更資料量
實現複雜度	容易實現，但受限於內存容量不易使用，擴充時需要人為實現	實現上較複雜，需要處理自動擴充的情境，但使用上較方便

Pros and Cons of Arrays