國外 IT 教育學院 Educative.io 創始人 Fahim ul Haq 寫過一篇過萬贊的文章《The top data structures you should know for your next coding interview》,總結了程序員面試中需要掌握的 8 種數據結構知識。

Fahim ul Haq 曾在 Facebook 和微軟任職，面試過不少程序員，所以這篇文章還是值得參考的。以下內容參考編譯自他的這篇《準備下次編程面試前你應該知道的數據結構》：

瑞典計算機科學家 Niklaus Wirth 在 1976 年寫了一本書，叫作《Algorithms + Data Structures = Programs》（算法+數據結構=程序）。

即便在 40 年后的今天，這條等式仍然成立。這也是為何程序員求職者應該向面試官展示出已經透徹理解了數據結構知識。

幾乎所有的面試問題都要求求職者表現出已經熟練掌握數據結構，不管你是剛畢業的應屆生還是工作了多年的老手，都是這樣。

有時，面試問題會明確提到數據結構，比如“給定一個二叉樹”；有時則比較含蓄，比如“我們想追蹤和每位作者相關的書籍數量。”

學習數據結構知識很有必要，哪怕你只是想找份比現在的工作更好的一份差事。我們首先了解數據結構的基本知識。

什么是數據結構？

簡單說，數據結構就是一個容器，以某種特定的布局存儲數據。這個“布局”使得數據結構在某些操作上非常高效，在另一些操作上則不那么高效。你的目標就是理解數據結構，這樣就能為手頭的問題選擇最優的數據結構。

為什么我們需要數據結構？

由于數據結構用來以有組織的形式存儲數據，而且數據是計算機科學中最重要的實體，因此數據結構的真正價值顯而易見。

無論你解決什么問題，你都必須以這種或那種方式處理數據比如員工的工資，股票價格，購物清單，甚至簡單的電話簿等等。

根據不同的場景，數據需要以特定格式存儲。目前有一些數據結構可以滿足我們以不同格式存儲數據的需求。

常用的數據結構

我們首先列出最常用的數據結構，然后再挨個講解：

數組

堆棧

隊列

鏈表

樹

圖

字典樹

哈希表

數組

數組是一種最簡單和最廣泛使用的數據結構，其它數據結構比如堆棧和隊列都源自數組。

下圖是一個大小為 4 的簡單數組，包含幾個元素（ 1 , 2 , 3，4）。

每個數據元素會被分配一個正的數值，叫作“索引”，它對應該元素在數組中的位置。大部分編程語言都將初始索引定義為 0.

以下是兩種數組：

一維數組（如上所示）

多維數組（數組的數組）

數組的基本操作：

Insert——在給定索引位置插入一個元素

Get——返回給定索引位置的元素

Delete——刪除給定索引位置的元素

Size——獲取數組內所有元素的總數

常問的數組面試問題：

找到數組中第二小的元素

找到數組中第一個沒有重復的整數

合并兩個分類數組

重新排列數組中的正值和負值

堆棧

我們都熟悉很有名的撤銷（Undo）選項，它幾乎存在每個應用程序中。有沒有想過它是如何工作的？其思路就是，按照最后的狀態排列在先的順序將工作的先前狀態（限于特定數字）存儲在內存中。這只用數組是無法實現的，因此堆棧就有了用武之地。

可以把堆棧看作一堆垂直排列的書籍。為了獲得位于中間位置的書，你需要拿掉放在它上面的所有書籍。這就是 LIFO（后進先出）方法的工作原理。

這是一個包含三個數據元素（1,2 和 3）的堆棧圖像，其中3位于頂部，首先把它刪除：

堆棧的基本操作：

Push——在頂部插入元素

Pop—— 從堆棧中刪除后返回頂部元素

isEmpty——如果堆棧為空，則返回 true

Top ——返回頂部元素，但不從堆棧中刪除

常見的堆棧面試問題：

使用堆棧計算后綴表達式

對堆棧中的值進行排序

檢查表達式中的括號是否平衡

隊列

與堆棧類似，隊列是另一種線性數據結構，以順序方式存儲元素。堆棧和隊列之間唯一的顯著區別是，隊列不是使用 LIFO 方法，而是應用 FIFO 方法，這是 First in First Out（先入先出）的縮寫。

隊列的完美現實例子：一列人在售票亭等候。如果有新人來，他們是從末尾加入隊列，而不是在開頭——站在前面的人將先買到票然后離開隊列。

下圖是一個包含四個數據元素（1,2,3 和 4）的隊列，其中 1 位于頂部，首先把它刪除：

隊列的基本操作：

Enqueue() —— 向隊列末尾插入元素

Dequeue() —— 從隊列頭部移除元素

isEmpty() —— 如果隊列為空，則返回 true

Top() —— 返回隊列的第一個元素

常問的隊列面試問題：

使用隊列來實現堆棧

顛倒隊列中前 k 個元素的順序

使用隊列生成從 1 到 n 的二進制數

鏈表

鏈表是另一個重要的線性數據結構，剛一看可能看起來像數組，但在內存分配，內部結構以及如何執行插入和刪除的基本操作方面有所不同。

鏈表就像一個節點鏈，其中每個節點包含數據和指向鏈中后續節點的指針等信息。有一個頭指針，指向鏈表的第一個元素，如果列表是空的，那么它只指向 null 或不指向任何內容。

鏈表用于實現文件系統，哈希表和鄰接表。下圖是鏈表內部結構的直觀展示：

下面是幾種類型的鏈表：

單鏈表（單向）

雙鏈表（雙向）

鏈表的基本操作：

InsertAtEnd —— 在鏈表末尾插入指定元素

InsertAtHead —— 在鏈表頭部插入指定元素

Delete —— 從鏈表中刪除指定元素

DeleteAtHead —— 刪除鏈表的第一個元素

Search —— 返回鏈表中的指定元素

isEmpty —— 如果鏈表為空，返回 true

常問的鏈表面試問題：

翻轉列表

檢測鏈表中的循環

返回鏈表中倒數第 n 個節點

移除鏈表中的重復值

圖

圖就是一組節點，以網絡的形式互相連接。節點也被稱為頂點（vertices）。一對（x,y）就叫做一個邊，表示頂點 x 和頂點 y 相連。一個邊可能包含權重/成本，顯示從頂點 x 到 y 所需的成本。

圖的類型：

無向圖

有向圖

在編程語言中，圖可以表示為兩種形式：

鄰接矩陣

鄰接列表

常見的圖遍歷算法：

廣度優先搜索

深度優先搜索

常問的圖面試問題：

實現廣度優先搜索和深度優先搜索

檢查一個圖是否為樹

計算一張圖中的邊的數量

找到兩個頂點之間的最短路徑

樹

樹是一種層級數據結構，包含了連接它們的頂點（節點）和邊。樹和圖很相似，但二者有個很大的不同點，即樹中沒有循環。

樹廣泛應用在人工智能和復雜的算法中，為解決各種問題提供高效的存儲機制。

下圖是一個簡單的樹，以及在樹型數據結構中所用的基本術語：

下面是幾種類型的樹：

N 叉樹

平衡樹

二叉樹

二叉搜索樹

平衡二叉樹

紅黑樹

2-3 樹

其中，二叉樹和二叉搜索樹是最常用的樹。

常問的樹面試問題：

找到一個二叉樹的高度

找到一個二叉搜索樹中第 k 個最大值

找到距離根部“k”個距離的節點

找到一個二叉樹中給定節點的祖先（ancestors）

字典樹

字典樹，也叫“前綴樹”，是一種樹形結構，在解決字符串相關問題中非常高效。其提供非常快速的檢索功能，常用于搜索字典中的單詞，為搜索引擎提供自動搜索建議，甚至能用于IP路由選擇。下面展示了 “top” “thus” 和 “their” 這三個詞是如何存儲在字典樹中的：

這些單詞以從上到下的方式存儲，其中綠色節點“p”，“s”和“r”分別表示“top”，“thus”和“their”的末尾。

常見的字典樹面試問題：

計算字典樹中的總字數

打印存儲在字典樹中的所有單詞

使用字典樹對數組的元素進行排序

使用字典樹從字典中形成單詞

構建一個T9字典

哈希表

散列是一個用于唯一標識對象并在一些預先計算的唯一索引（稱為“密鑰”）存儲每個對象的過程。因此，對象以“鍵值”對的形式存儲，這些項的集合被稱為“字典”。可以使用該鍵值搜索每個對象。有多種不同的基于哈希的數據結構，但最常用的數據結構是哈希表。

哈希表通常使用數組實現。

哈希數據結構的性能取決于以下三個因素：

哈希函數

哈希表的大小

碰撞處理方法

下圖展示了如何在數組中映射哈希。該數組的索引是通過哈希函數計算的。

常問的哈希面試問題：

找到數組中的對稱對

追蹤遍歷的完整路徑

查看一個數組是否為另一個數組的子集

檢查給定數組是否不相交

以上就是你在準備編程面試前需要掌握的 8 種數據結構。