# 幾種基本的數據結構
> 圖引自『我的第一本算法書』第一章
## 1.鏈表
### 概念圖
如下圖,`Blue`、`Yellow`、`Red`三個字符串存儲于鏈表中,每個數據都有一個『指針』,它指向下一個數據的內存地址(`Red`是最后一個數據,其指針不指向任何位置)。

### 在內存中存儲
由上述內容可知,在鏈表中,數據無需存儲在連續空間內,一般都是分散存儲的。

### 訪問方式 - 順序訪問
因為數據是分散存儲的,所以想要訪問一個數據,只能從第一個數據開始,順著指針往下找。比如,想查找`Red`,查找順序如下:
`Blue` -> `Yellow` -> `Red`(Done)
查找數據的耗時和鏈表長度`n`有關,時間復雜度為:
O(n)
### 添加數據
如果想添加數據,只需改變添加位置前后的指針指向即可,比如『在`Blue`和`Yellow`直接添加`Green`』:

添加數據的耗時和鏈表長度`n`無關,如果已經到達需要添加數據的位置,則時間復雜度為:
O(1)
### 刪除數據
刪除數據也一樣,我們只需要改變指針的指向即可,比如『刪除`Yellow`』:

此時,`Yellow`本身還存在,不過沒關系,它已經無法被訪問,今后需要用到其所在存儲空間時,直接覆蓋掉即可。
和『添加數據』一樣,刪除數據的時間復雜度為:
O(1)
### 特點
由上述內容我們可以看出,鏈表有以下特點:
* 數據呈線性排列,分散存儲
* 訪問比較耗時 O(n)
* 數據的添加和刪除都比較方便 O(1)
## 2.數組
### 概念圖
數組也是線性排列的,它的結構和最開始講的『按姓名首字母排序的電話薄』類似。

### 在內存中存儲
數組的數據按順序存放在連續空間內:

### 訪問方式 - 隨機訪問
因為數據存放在連續空間內,所以我們可以用數組下標計算出每個數據的內存位置,借此直接訪問目標數據,這叫做『隨機訪問』:

我們可以通過數組下標查找目標數據,查找數據的耗時和數組長度`n`無關,時間復雜度恒為:
O(n)
### 添加數據
如果想添加數據,需要經過以下步驟:
① 在數組末位增加存儲空間
② 從新數據要存放的位置,把后面已有數據一個個后移
③ 插入新數據
例如,我們嘗試將`Green`添加到第二個位置上:

添加數據的耗時和鏈表長度`n`有關,如果在數組頭部添加數據,則時間復雜度為:
O(n)
### 刪除數據
刪除數據是將『添加數據』反過來操作一遍,需要經過以下步驟:
① 刪除目標數據
② 把目標數據后面已有數據一個個往前移
③ 刪除末尾多余空間


和『添加數據』一樣,刪除數據的時間復雜度為:
O(n)
### 特點
由上述內容我們可以看出,數組有以下特點:
* 數據呈線性排列,連續存儲
* 訪問快速 O(1)
* 數據的添加和刪除比較復雜 O(n)
### 和鏈表對比
通過對比,我們可以根據哪種操作頻繁來決定使用哪種數據結構。
|訪問|添加|刪除
---|---|---|
鏈表|慢|快|快
數組|快|慢|慢
## 3.棧
### 概念圖
棧也是線性排列的。棧就像一摞書,新書都會被堆在最上面,取書時也只能從最上面開始取。

### 添加數據 - 入棧(`push`)
往棧中添加數據的操作叫做**入棧(`push`)**
添加`Green`:

添加`Red`:

### 取出數據 - 出棧(`pop`)
從棧中取出數據的操作叫做**出棧**(`pop`)
例,我們要取出`Green`:
① 先取出`Red`:

② 這時`Green`在頂部,才能通過出棧操作取出:

# 代碼庫地址
[https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)
### 特點
由上述內容我們可以看出,棧有以下特點:
* 『后進先出』,Last In First Out (LIFO)
* 添加和刪除數據只能在一端進行
* 只能訪問到頂端的數據
* 要想訪問中間的數據,必須通過出棧操作將目標數據移到棧頂
* 很適合『只需要訪問最新數據』的情況
## 4.隊列
### 概念圖
隊列也是線性排列的。隊列就像排隊取款的人,只能從前面往后處理,新來的人只能排在隊尾。

### 添加數據 - 入列
往隊列中添加數據的操作叫做**入列**
添加`Green`:

添加`Red`:

### 取出(刪除)數據 - 出列
從隊列中取出(刪除)數據的操作叫做**出列**
例,我們要取出`Green`:
① 先取出(刪除)`Blue`:

② 這時`Green`在頭部,才能通過出列操作取出(刪除):

### 特點
由上述內容我們可以看出,隊列有以下特點:
* 『先進先出』,First In First Out (FIFO)
* 添加和刪除數據是在兩端進行的(添加-尾端,刪除-頭部)
* 只能訪問到頭部的數據
* 要想訪問中間的數據,必須通過出列操作將目標數據移到頭部
* 很適合『先來的數據先處理』的情況