十種典型的數(shù)據(jù)結(jié)構(gòu)及其特性

數(shù)據(jù)結(jié)構(gòu)是軟件開(kāi)發(fā)的關(guān)鍵部分，也是開(kāi)發(fā)人員面試經(jīng)常遇到的問(wèn)題，它們通常以專用的格式進(jìn)行數(shù)據(jù)組織和存儲(chǔ)。本文我們將會(huì)介紹十種典型的數(shù)據(jù)結(jié)構(gòu)及其特性。需要注意的是，雖然一些數(shù)據(jù)結(jié)構(gòu)包含了時(shí)間復(fù)雜度O，但不完全都有因?yàn)闀r(shí)間復(fù)雜度很多時(shí)候與你的代碼書(shū)寫(xiě)有關(guān)。實(shí)際使用時(shí)，大多數(shù)的數(shù)學(xué)結(jié)構(gòu)都不需要你自己實(shí)現(xiàn)它們，除非像C語(yǔ)言這樣的底層語(yǔ)言。雖然大多數(shù)高級(jí)語(yǔ)言一般都會(huì)內(nèi)置這些數(shù)據(jù)結(jié)構(gòu)，但如果你知道如何實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)將會(huì)為你在開(kāi)發(fā)工作中帶來(lái)巨大優(yōu)勢(shì)，說(shuō)不定當(dāng)你嘗試編寫(xiě)高性能代碼時(shí)就會(huì)派上用場(chǎng)。

1. 鏈表

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

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

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

2. 堆棧

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

堆棧遵循后進(jìn)先出，也就是說(shuō)你最后放入堆棧的項(xiàng)目是第一個(gè)出棧的項(xiàng)目。

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

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

3.隊(duì)列

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

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

隊(duì)列時(shí)間復(fù)雜度:

4.集合

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

并集，將來(lái)自兩個(gè)不同集合的所有元素結(jié)合起來(lái)作為新集合返回（不重復(fù)）.

交集，給定兩個(gè)集合，此函數(shù)返回另一個(gè)集合，包含屬于兩個(gè)集合的共同部分。

差集，給定兩個(gè)集合，此函數(shù)返回另一個(gè)集合，其中各個(gè)元素屬于一個(gè)集合，但不屬于另一個(gè)集合。

子集 ，返回一個(gè)布爾值，顯示一個(gè)集合中的所有元素是否包含在不同的集合中。

5. MAP

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

在集合中增加一對(duì)

從集合中刪除一對(duì)

修改現(xiàn)有的一對(duì)

查找與特定鍵相關(guān)聯(lián)的值

6.哈希表

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

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

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

7.二叉搜索樹(shù)

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

每棵樹(shù)都有一個(gè)根節(jié)點(diǎn)（位于頂部）。

根節(jié)點(diǎn)具有零個(gè)或多個(gè)子節(jié)點(diǎn)。

每個(gè)子節(jié)點(diǎn)都有零個(gè)或多個(gè)子節(jié)點(diǎn)。

二叉搜索樹(shù)還具有額外的兩個(gè)特征：

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn).

對(duì)于每個(gè)節(jié)點(diǎn)，它左邊的子節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)，而右邊的子節(jié)點(diǎn)則大于當(dāng)前節(jié)點(diǎn)。

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。

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

二叉樹(shù)時(shí)間復(fù)雜度:

8. 前綴樹(shù)或字典樹(shù)

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

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

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

9.二叉堆

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

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

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

二叉堆時(shí)間復(fù)雜度:

10. 圖

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

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

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

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

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

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

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

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