• 普通的程序員只關注代碼，但優秀的程序員更在意數據結構和彼此間的聯系。

— Linus Torvalds, Linux之父

數據結構是軟件開發的關鍵部分，也是開發人員面試經常遇到的問題，它們通常以專用的格式進行數據組織和存儲。本文我們將會介紹十種典型的數據結構及其特性。

需要注意的是，雖然一些數據結構包含了時間復雜度O，但不完全都有因為時間復雜度很多時候與你的代碼書寫有關。

實際使用時，大多數的數學結構都不需要你自己實現它們，除非像C語言這樣的底層語言。雖然大多數高級語言一般都會內置這些數據結構，但如果你知道如何實現這些數據結構將會為你在開發工作中帶來巨大優勢，說不定當你嘗試編寫高性能代碼時就會派上用場。

1. 鏈表

鏈表屬于最基本的數據結構。由于許多數據結構既可以用數組也可以用鏈表來實現，所以通常會與數組進行比較，但它們各有優缺點。

 

鏈表通常由一組代表一個序列的節點組成。 每個節點包含存儲的任意類型實際數據以及指向序列中下一個節點的指針。特殊的，還有雙向鏈表，其中每個節點都有兩個指針，分別起到承前啟后的作用。

鏈表中最基本的操作是插入鏈表、刪除鏈表以及查詢鏈表。下表為鏈表的時間復雜度：

 

2. 堆棧

堆棧屬于一種基本的數據結構，你只能在堆棧的頂部插入或刪除項目。這有點像一堆書， 如果你想看堆棧中間的一本書，你必須先將它上面上面的所有書移走。

堆棧遵循后進先出，也就是說你***放入堆棧的項目是***個出棧的項目。

 

對堆棧主要有三種操作：push，即插入新內容到堆棧;pop，從堆棧中刪除一項內容;pip，顯示堆棧的內容。

堆棧時間復雜度：

 

3.隊列

你可以把隊列想象成一家雜貨店里排隊買單的人，隊伍中***個人先被服務。

 

隊列遵循先進先出，也就是說一旦你想添加了新元素，你要想刪除它，必須先刪除它前面的的所有元素。隊列只有兩個主要操作：入隊和出隊。 入隊，就是將新的內容插入隊列后面，而出隊就是前面所有的內容。

隊列時間復雜度：

 

4.集合

 

以集合形式存儲的數據結構中不存在任何特定的順序，也不存在重復的值。除了向集合中添加新元素或者刪除元素之外，還有一些重要的集合函數可以進行兩組集合的處理。

• 并集，將來自兩個不同集合的所有元素結合起來作為新集合返回(不重復).
• 交集，給定兩個集合，此函數返回另一個集合，包含屬于兩個集合的共同部分。
• 差集，給定兩個集合，此函數返回另一個集合，其中各個元素屬于一個集合，但不屬于另一個集合。
• 子集 ，返回一個布爾值，顯示一個集合中的所有元素是否包含在不同的集合中。

5. MAP

Map是容器的一種，也屬于一種數據結構，它將數據存儲在鍵/值對中，且每個鍵是唯一的。 map有時也稱為關聯數組或字典，通常被用于快速查找數據。 Map可以進行以下操作：

 

• 在集合中增加一對
• 從集合中刪除一對
• 修改現有的一對
• 查找與特定鍵相關聯的值

6.哈希表

 

哈希表是包含鍵/值對的地圖數據結構，使用散列函數來把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。散列函數通常將一個字符串作為輸入，并輸出一個數值。散列函數對相同的輸入提供相同的輸出編號。 當兩個輸入哈希得到相同的數字輸出時，稱為碰撞。

我們的目標是沒有碰撞。所以當你將一個鍵/值對輸入到一個散列表中時，這個鍵將通過散列函數映射到一個數字，用作值存儲的實際鍵。 當你嘗試再次訪問相同的密鑰時，哈希函數將處理該密鑰并返回相同的數字結果，用于查找關聯的值。 算法速度非常快，查找的時間復雜度僅為O(1)。

Hash table 時間復雜度：

 

7.二叉搜索樹

 

樹是由節點組成的數據結構，它具有以下特征：

• 每棵樹都有一個根節點(位于頂部)。
• 根節點具有零個或多個子節點。
• 每個子節點都有零個或多個子節點。

二叉搜索樹還具有額外的兩個特征：

• 每個節點最多有兩個子節點.
• 對于每個節點，它左邊的子節點小于當前節點，而右邊的子節點則大于當前節點。
• 每個節點最多有兩個子節點。

二叉搜索樹允許快速查找、添加和刪除內容。 從它的設計結構來看，每次比較后都會跳過樹的大約一半內容，因此每次查找、插入或刪除需要的操作時間與存儲在樹中的內容數量的對數成比例。

二叉樹時間復雜度：

 

8. 前綴樹或字典樹

 

前綴樹或字典樹,是一種搜索樹。 前綴樹中存儲數據的每個步驟其實就是操作一個節點，它通常被用來存儲單詞，可以進行快速查找，例如單詞自動構成功能。

語言字典樹中的每個節點都包含一個單詞的一個字母。 你可以按照樹狀結構的一條分支拼寫出一個單詞。 當字母的順序與字典中的其他單詞不同或者一個單詞完成時，開始分支。每個節點都包含一個字母(數據)和一個布爾值(用于指示該節點是否是單詞中的***一個節點)。

看看上面的圖像，你可以構成很多單詞。從頂部的根節點開始并往下，這個字典樹包含了ball, bat, doll, do, dork, dorm, send, sense這些單詞。

9.二叉堆

 

二叉堆是特殊的樹數據結構。形式上看，它從頂點開始，每個節點有兩個子節點，每個子節點又各自有自己的兩個子節點;數值上看，每個節點的兩個子節點都比它大或小。

二叉堆有兩種：***堆和最小堆。***堆：父結點的鍵值總是大于或等于任何一個子節點的鍵值;最小堆：父結點的鍵值總是小于或等于任何一個子節點的鍵值。

在二叉堆上可以進行插入節點、刪除節點、取出值最小的節點、減小節點的值等基本操作。不同層之間的順序很重要，但同一層上節點的順序無關緊要。 如圖所示，你可以看到最小堆的第三層的值是10，6和12，這些數字并不是按照順序排列的。

二叉堆時間復雜度：

 

10. 圖

圖是由節點(也稱為頂點)與它們之間的連接(稱為邊)構成的集合。圖也被稱為網絡。

社交網絡是典型的圖的例子，節點是人，邊代表他們互相認識的關系。

 

主要有兩種類型的圖：有向和無向。無向圖是指在節點之間的邊上沒有任何方向的圖。相反，有向圖表示每條邊上都有方向的圖。

表示圖的兩種常用方式是鄰接表和鄰接矩陣：

 

鄰接列表，表示一個列表的左側是節點，右側列出了它所連接的所有其他節點。

鄰接矩陣，則是一個數字網格。其中每個行或列表示圖中的不同節點。每一行和一列的交點是一個表示關系的數字。0表示沒有邊或沒有關系，1表示有一種關系，而大于1的數字則可表示不同的權重。

通過遍歷算法可以遍歷或訪問圖中的節點。遍歷算法的主要類型有廣度優先搜索和深度優先搜索，可以被用于確定節點與根節點的接近程度。觀看下面的視頻你可以學習到如何在JavaScript中實現廣度優先搜索。

鄰接列表的時間復雜度：

 

來源：Medium