陣列(Array)

介紹

數據排成一列，儲存在連續的記憶體位置，在大多數的演算法中都經常會使用到，可以把它想像成停車場，每一輛車就是資料，停車格的號碼就是在陣列中的位置。

以下為陣列特性:

連續的記憶體位置
儲存相同類型的資料
擁有緩存局部性，能夠提高性能
隨機訪問速度快
插入刪除花費成本較大

在陣列當中就包含元素和索引，如下圖所示

元素Element - 在陣列當中的每一個位置的項目。
索引Index - 陣列中元素的每個內存位置都由數字索引標識。

陣列 vs. 鏈結串列

	存取	插入	刪除
陣列`Array`	快	慢	慢
鏈結串列`Linked list`	慢	快	快

複雜度

時間複雜度

Action動作	平均	最壞
訪問`(Access)`	$O(1)$	$O(1)$
搜尋`(Search)`	$O(n)$	$O(n)$
插入`(Insertion)`	$O(n)$	$O(n)$
刪除`(Deletion)`	$O(n)$	$O(n)$

空間複雜度

$O(n)$

基本操作

以下為陣列常見操作

遍歷: 依次遍歷所有陣列元素。
搜索: 使用給定索引或按值搜索元素。
插入: 在給定位置添加一個元素。
刪除: 刪除給定位置的元素。
更新: 更新給定索引處的元素。
排序: 按特定順序排列陣列中的元素。
合併: 將兩個陣列合併為一個。
反轉: 將陣列順序顛倒

遍歷

走訪陣列內每個元素

let array = [1,2,5,3,4,8]

for (let i = 0; i < array.length; i++) {
    console.log(array[i])
}

搜尋

給定索引或按值搜索元素

let array = [1,2,5,3,4,8]
// 按值搜索元素
let index = array.indexOf(5)
console.log(index) // 2

// 給定索引
let element = array[index]
console.log(element) // 5

插入

將新的元素插入陣列

let array = [1,2,5,3,4,8]
array.splice(2, 0, 6)
console.log(array) // [1, 2, 6, 5, 3, 4, 8]

刪除

陣列內刪除特定位置的元素

let array = [1, 2, 6, 5, 3, 4, 8]
array.splice(2, 1)
console.log(array) // [1, 2, 5, 3, 4, 8]

更新

更新給定位置的元素

let array = [1, 2, 5, 3, 4, 8]
array.splice(2, 1, 7)
console.log(array) // [1, 2, 7, 3, 4, 8]

排序

排序陣列

let array = [1, 2, 7, 3, 4, 8]
array.sort()
console.log(array) // [1, 2, 3, 4, 7, 8]

合併

將A陣列與B陣列組合

let array = [1, 2, 3, 4, 7, 8]
let array2 = [9, 10]
let array3 = array.concat(array2)
console.log(array3) // [1, 2, 3, 4, 7, 8, 9, 10]

反轉陣列

將陣列內順序顛倒

let array = [1, 2, 3, 4, 7, 8, 9, 10]
array.reverse()
console.log(array) // [10, 9, 8, 4, 3, 7, 2, 1]

補充

為什麼緩存位置對陣列性能很重要？

MDN JavaScript Array