常見的(de)8種數據結構

1976 年，一(yī / yì ／yí)個(gè)瑞士計算機科學家寫一(yī / yì ／yí)本書 《Algorithms + Data Structures = Programs》。即：算法 + 數據結構 = 程序。40 多年過去了(le／liǎo)，這(zhè)個(gè)等式依然成立。

很多代碼面試題都要(yào / yāo)求候選者深入理解數據結構，不(bù)管你來(lái)自大(dà)學計算機專業還是(shì)編程培訓機構，也(yě)不(bù)管你有多少年編程經驗。有時(shí)面試題會直接提到(dào)數據結構，比如“給我實現一(yī / yì ／yí)個(gè)二叉樹”，然而(ér)有時(shí)則不(bù)那麽明顯，比如“統計一(yī / yì ／yí)下每個(gè)作者寫的(de)書的(de)數量”。

什麽是(shì)數據結構？

數據結構是(shì)計算機存儲、組織數據的(de)方式。對于(yú)特定的(de)數據結構(比如數組)，有些操作效率很高(讀某個(gè)數組元素)，有些操作的(de)效率很低(删除某個(gè)數組元素)。程序員的(de)目标是(shì)爲(wéi / wèi)當前的(de)問題選擇最優的(de)數據結構。

爲(wéi / wèi)什麽我們需要(yào / yāo)數據結構？

數據是(shì)程序的(de)核心要(yào / yāo)素，因此數據結構的(de)價值不(bù)言而(ér)喻。無論你在(zài)寫什麽程序，你都需要(yào / yāo)與數據打交道(dào)，比如員工工資、股票價格、雜貨清單或者電話本。在(zài)不(bù)同場景下，數據需要(yào / yāo)以(yǐ)特定的(de)方式存儲，我們有不(bù)同的(de)數據結構可以(yǐ)滿足我們的(de)需求。

8 種常用數據結構

1. 數組
2. 棧
3. 隊列
4. 鏈表
5. 圖
6. 樹
7. 前綴樹
8. 哈希表

1. 數組

數組(Array)大(dà)概是(shì)最簡單，也(yě)是(shì)最常用的(de)數據結構了(le／liǎo)。其他(tā)數據結構，比如棧和(hé / huò)隊列都是(shì)由數組衍生出(chū)來(lái)的(de)。

下圖展示了(le／liǎo) 1 個(gè)數組，它有 4 個(gè)元素：

每一(yī / yì ／yí)個(gè)數組元素的(de)位置由數字編号，稱爲(wéi / wèi)下标或者索引(index)。大(dà)多數編程語言的(de)數組第一(yī / yì ／yí)個(gè)元素的(de)下标是(shì) 0。

根據維度區分，有 2 種不(bù)同的(de)數組：

• 一(yī / yì ／yí)維數組(如上(shàng)圖所示)
• 多維數組(數組的(de)元素爲(wéi / wèi)數組)

數組的(de)基本操作

• Insert - 在(zài)某個(gè)索引處插入元素
• Get - 讀取某個(gè)索引處的(de)元素
• Delete - 删除某個(gè)索引處的(de)元素
• Size - 獲取數組的(de)長度

2. 棧

撤回，即 Ctrl+Z，是(shì)我們最常見的(de)操作之(zhī)一(yī / yì ／yí)，大(dà)多數應用都會支持這(zhè)個(gè)功能。你知道(dào)它是(shì)怎麽實現的(de)嗎？答案是(shì)這(zhè)樣的(de)：把之(zhī)前的(de)應用狀态(限制個(gè)數)保存到(dào)内存中，最近的(de)狀态放到(dào)第一(yī / yì ／yí)個(gè)。這(zhè)時(shí)，我們需要(yào / yāo)棧(stack)來(lái)實現這(zhè)個(gè)功能。

棧中的(de)元素采用 LIFO (Last In First Out)，即後進先出(chū)。

下圖的(de)棧有 3 個(gè)元素，3 在(zài)最上(shàng)面，因此它會被第一(yī / yì ／yí)個(gè)移除：

棧的(de)基本操作

• Push — 在(zài)棧的(de)最上(shàng)方插入元素
• Pop — 返回棧最上(shàng)方的(de)元素，并将其删除
• isEmpty — 查詢棧是(shì)否爲(wéi / wèi)空
• Top — 返回棧最上(shàng)方的(de)元素，并不(bù)删除

3. 隊列

隊列(Queue)與棧類似，都是(shì)采用線性結構存儲數據。它們的(de)區别在(zài)于(yú)，棧采用 LIFO 方式，而(ér)隊列采用先進先出(chū)，即FIFO(First in First Out)。

下圖展示了(le／liǎo)一(yī / yì ／yí)個(gè)隊列，1 是(shì)最上(shàng)面的(de)元素，它會被第一(yī / yì ／yí)個(gè)移除：

隊列的(de)基本操作

• Enqueue — 在(zài)隊列末尾插入元素
• Dequeue — 将隊列第一(yī / yì ／yí)個(gè)元素删除
• isEmpty — 查詢隊列是(shì)否爲(wéi / wèi)空
• Top — 返回隊列的(de)第一(yī / yì ／yí)個(gè)元素

4. 鏈表

鏈表(Linked List)也(yě)是(shì)線性結構，它與數組看起來(lái)非常像，但是(shì)它們的(de)内存分配方式、内部結構和(hé / huò)插入删除操作方式都不(bù)一(yī / yì ／yí)樣。

鏈表是(shì)一(yī / yì ／yí)系列節點組成的(de)鏈，每一(yī / yì ／yí)個(gè)節點保存了(le／liǎo)數據以(yǐ)及指向下一(yī / yì ／yí)個(gè)節點的(de)指針。鏈表頭指針指向第一(yī / yì ／yí)個(gè)節點，如果鏈表爲(wéi / wèi)空，則頭指針爲(wéi / wèi)空或者爲(wéi / wèi) null。

鏈表可以(yǐ)用來(lái)實現文件系統、哈希表和(hé / huò)鄰接表。

下圖展示了(le／liǎo)一(yī / yì ／yí)個(gè)鏈表，它有 3 個(gè)節點：

鏈表分爲(wéi / wèi) 2 種：

• 單向鏈表
• 雙向鏈表

鏈表的(de)基本操作

• InsertAtEnd — 在(zài)鏈表結尾插入元素
• InsertAtHead — 在(zài)鏈表開頭插入元素
• Delete — 删除鏈表的(de)指定元素
• DeleteAtHead — 删除鏈表第一(yī / yì ／yí)個(gè)元素
• Search — 在(zài)鏈表中查詢指定元素
• isEmpty — 查詢鏈表是(shì)否爲(wéi / wèi)空

5. 圖

圖(graph)由多個(gè)節點(vertex)構成，節點之(zhī)間闊以(yǐ)互相連接組成一(yī / yì ／yí)個(gè)網絡。(x, y)表示一(yī / yì ／yí)條邊(edge)，它表示節點 x 與 y 相連。邊可能會有權值(weight/cost)。

圖分爲(wéi / wèi)兩種:

• 無向圖
• 有向圖

在(zài)編程語言中，圖有可能有以(yǐ)下兩種形式表示：

• 鄰接矩陣(Adjacency Matrix)
• 鄰接表(Adjacency List)

遍曆圖有兩周算法

• 廣度優先搜索(Breadth First Search)
• 深度優先搜索(Depth First Search)

6. 樹

樹(Tree)是(shì)一(yī / yì ／yí)個(gè)分層的(de)數據結構，由節點和(hé / huò)連接節點的(de)邊組成。樹是(shì)一(yī / yì ／yí)種特殊的(de)圖，它與圖最大(dà)的(de)區别是(shì)沒有循環。

樹被廣泛應用在(zài)人(rén)工智能和(hé / huò)一(yī / yì ／yí)些複雜算法中，用來(lái)提供高效的(de)存儲結構。

下圖是(shì)一(yī / yì ／yí)個(gè)簡單的(de)樹以(yǐ)及與樹相關的(de)術語：

樹有很多分類：

• N 叉樹(N-ary Tree)
• 平衡樹(Balanced Tree)
• 二叉樹(Binary Tree)
• 二叉查找樹(Binary Search Tree)
• 平衡二叉樹(AVL Tree)
• 紅黑樹(Red Black Tree)
• 2-3 樹(2–3 Tree)

其中，二叉樹和(hé / huò)二叉查找樹是(shì)最常用的(de)樹。

7. 前綴樹

前綴樹(Prefix Trees 或者 Trie)與樹類似，用于(yú)處理字符串相關的(de)問題時(shí)非常高效。它可以(yǐ)實現快速檢索，常用于(yú)字典中的(de)單詞查詢，搜索引擎的(de)自動補全甚至 IP 路由。

下圖展示了(le／liǎo)“top”, “thus”和(hé / huò)“their”三個(gè)單詞在(zài)前綴樹中如何存儲的(de)：

單詞是(shì)按照字母從上(shàng)往下存儲，“p”, “s”和(hé / huò)“r”節點分别表示“top”, “thus”和(hé / huò)“their”的(de)單詞結尾。

8. 哈希表

哈希(Hash)将某個(gè)對象變換爲(wéi / wèi)唯一(yī / yì ／yí)标識符，該标識符通常用一(yī / yì ／yí)個(gè)短的(de)随機字母和(hé / huò)數字組成的(de)字符串來(lái)代表。哈希可以(yǐ)用來(lái)實現各種數據結構，其中最常用的(de)就(jiù)是(shì)哈希表(hash table)。

哈希表通常由數組實現。

哈希表的(de)性能取決于(yú) 3 個(gè)指标：

• 哈希函數
• 哈希表的(de)大(dà)小
• 哈希沖突處理方式

下圖展示了(le／liǎo)有數組實現的(de)哈希表，數組的(de)下标即爲(wéi / wèi)哈希值，由哈希函數計算，作爲(wéi / wèi)哈希表的(de)鍵(key)，而(ér)數組中保存的(de)數據即爲(wéi / wèi)值(value)：