---
# System prepended metadata

title: 資結筆記｜陣列（array）
tags: [資料結構]

---

## 資結筆記｜陣列（array）

### 基本概念

&emsp;&emsp;所謂的<font color="#0000FF">陣列</font>（array）就是指將資料放在<font color="#f00">連續</font>的記憶體空間，其中的每筆資料我們稱為<font color="#0000FF">元素</font>。因為是連續的空間所以我們可以依序幫每個空間編號稱為<font color="#0000FF">索引</font>（index）見下圖。

| 索引index | 0 | 1 | 2 | 3 | 4 |    5 |
| --------- | ---- | ---- | ---- | ---- | ---- | --- |
| 資料內容  | 9    | 5    | 8    | 2    |      |     |


<br/>

### 存取陣列內容

&emsp;&emsp;通常我們索引會從0開始，假設我們的陣列為x，要提取內容8，不用從頭開始找，可以直接使用所以2取得，這種讀取方式叫做<font color="#0000FF">隨機存取</font>（random access）；反之如果要從頭開始一個個找，我們稱為循序存取（sequential access）。

| 索引index | x[0] | x[1] | x[2] | x[3] | x[4] |    x[5] |
| --------- | ---- | ---- | ---- | ---- | ---- | --- |
| 資料內容  | 9    | 5    | 8    | 2    |      |     |

<br/>

### 新增或刪除陣列中的元素

&emsp;&emsp;陣列存取雖然很方便，但新增跟刪除內容都十分麻煩。假設要新增一組資料6在索引1的位置，則需要將x[1]後所有的資料向後移動，如下表格，

| 索引index | x[0] | x[1] | x[2] | x[3] | x[4] |   x[5]  |
| --------- | ---- | ---- | ---- | ---- | ---- | --- |
| 資料內容  | 9    |   <font color="#f00">6</font>  |   <font color="#0000FF">5</font>  | <font color="#0000FF">8</font>    |   <font color="#0000FF">2</font>  |     |

<br/>

&emsp;&emsp;假設要刪除索引2的資料，則需將所有x[2]後的資料向前移動，如下圖，

| 索引index | x[0] | x[1] | x[2] | x[3] | x[4] |   x[5]  |
| --------- | ---- | ---- | ---- | ---- | ---- | --- |
| 資料內容  | 9    |   6  |   <font color="#0000FF">8</font>  | <font color="#0000FF">2</font>    |     |     |

&emsp;&emsp;上述新增跟刪除資料，最糟的情況時間複雜度是 $O(n)$。

<br/>

### 陣列（array）的優缺點

優點：結構簡單好用、容易理解，讀取陣列的速度很快
缺點：插入刪除資料沒效率



| 陣列結構   | 讀取 | 插入 | 刪除 | 搜尋（已排序） |  搜尋（未排序）   |
| ---------- | ---- | ---- | ---- | -------------- | --- |
| 時間複雜度 | $O(1)$ | $O(n)$ |  $O(n)$    |       $O(logn)$          |  $O(n)$   |

<br/>

以上就是最基本的茲列處存在電腦中的方式陣列（array）有沒有很簡單。