• 普通的程序員只關(guān)注代碼，但優(yōu)秀的程序員更在意數(shù)據(jù)結(jié)構(gòu)和彼此間的聯(lián)系。

— Linus Torvalds, Linux之父

數(shù)據(jù)結(jié)構(gòu)是軟件開發(fā)的關(guān)鍵部分，也是開發(fā)人員面試經(jīng)常遇到的問題，它們通常以專用的格式進行數(shù)據(jù)組織和存儲。本文我們將會介紹十種典型的數(shù)據(jù)結(jié)構(gòu)及其特性。

需要注意的是，雖然一些數(shù)據(jù)結(jié)構(gòu)包含了時間復(fù)雜度O，但不完全都有因為時間復(fù)雜度很多時候與你的代碼書寫有關(guān)。

實際使用時，大多數(shù)的數(shù)學(xué)結(jié)構(gòu)都不需要你自己實現(xiàn)它們，除非像C語言這樣的底層語言。雖然大多數(shù)高級語言一般都會內(nèi)置這些數(shù)據(jù)結(jié)構(gòu)，但如果你知道如何實現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)將會為你在開發(fā)工作中帶來巨大優(yōu)勢，說不定當(dāng)你嘗試編寫高性能代碼時就會派上用場。

1. 鏈表

鏈表屬于最基本的數(shù)據(jù)結(jié)構(gòu)。由于許多數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組也可以用鏈表來實現(xiàn)，所以通常會與數(shù)組進行比較，但它們各有優(yōu)缺點。

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

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

2. 堆棧

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

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

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

堆棧時間復(fù)雜度：

3.隊列

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

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

隊列時間復(fù)雜度：

4.集合

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

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

5. MAP

Map是容器的一種，也屬于一種數(shù)據(jù)結(jié)構(gòu)，它將數(shù)據(jù)存儲在鍵/值對中，且每個鍵是唯一的。 map有時也稱為關(guān)聯(lián)數(shù)組或字典，通常被用于快速查找數(shù)據(jù)。 Map可以進行以下操作：

• 在集合中增加一對
• 從集合中刪除一對
• 修改現(xiàn)有的一對
• 查找與特定鍵相關(guān)聯(lián)的值

6.哈希表

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

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

Hash table 時間復(fù)雜度：

7.二叉搜索樹

樹是由節(jié)點組成的數(shù)據(jù)結(jié)構(gòu)，它具有以下特征：

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

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

• 每個節(jié)點最多有兩個子節(jié)點.
• 對于每個節(jié)點，它左邊的子節(jié)點小于當(dāng)前節(jié)點，而右邊的子節(jié)點則大于當(dāng)前節(jié)點。
• 每個節(jié)點最多有兩個子節(jié)點。

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

二叉樹時間復(fù)雜度：

8. 前綴樹或字典樹

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

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

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

9.二叉堆

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

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

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

二叉堆時間復(fù)雜度：

10. 圖

圖是由節(jié)點(也稱為頂點)與它們之間的連接(稱為邊)構(gòu)成的集合。圖也被稱為網(wǎng)絡(luò)。

社交網(wǎng)絡(luò)是典型的圖的例子，節(jié)點是人，邊代表他們互相認(rèn)識的關(guān)系。

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

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

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

鄰接矩陣，則是一個數(shù)字網(wǎng)格。其中每個行或列表示圖中的不同節(jié)點。每一行和一列的交點是一個表示關(guān)系的數(shù)字。0表示沒有邊或沒有關(guān)系，1表示有一種關(guān)系，而大于1的數(shù)字則可表示不同的權(quán)重。

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

鄰接列表的時間復(fù)雜度：

來源：Medium