## 資結筆記｜陣列（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）有沒有很簡單。