---
tags: 資料結構, LeetCode
disqus: HackMD
---

# 陣列(Array)

:::spoiler 文章目錄
[toc]
:::

## 介紹

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

以下為陣列特性:

* 連續的記憶體位置
* 儲存相同類型的資料
* 擁有[緩存局部性](https://en.wikipedia.org/wiki/Locality_of_reference)，能夠提高性能
* 隨機訪問速度快
* 插入刪除花費成本較大

(圖片來自於[geeksforgeeks](https://www.geeksforgeeks.org/what-is-array/?ref=lbp))

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

* 元素`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]

## 補充

[為什麼緩存位置對陣列性能很重要？](https://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance)

[MDN JavaScript Array](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/Array)