數(shù)據(jù)結(jié)構(gòu)分類

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成 。

常用的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組，棧，鏈表，隊(duì)列，樹，圖，堆，散列表等，如圖所示：

每一種數(shù)據(jù)結(jié)構(gòu)都有著獨(dú)特的數(shù)據(jù)存儲方式，下面為大家介紹它們的結(jié)構(gòu)和優(yōu)缺點(diǎn)。

（1）數(shù)組

數(shù)組是可以再內(nèi)存中連續(xù)存儲多個元素的結(jié)構(gòu)，在內(nèi)存中的分配也是連續(xù)的，數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問，數(shù)組下標(biāo)從0開始。例如下面這段代碼就是將數(shù)組的第一個元素賦值為 1。

int[] data = new int[100]；data[0]  = 1;

優(yōu)點(diǎn)：

1. 按照索引查詢元素速度快

2. 按照索引遍歷數(shù)組方便

缺點(diǎn)：

1. 數(shù)組的大小固定后就無法擴(kuò)容了

2. 數(shù)組只能存儲一種類型的數(shù)據(jù)

3. 添加，刪除的操作慢，因?yàn)橐苿悠渌脑亍?/p>

適用場景：

頻繁查詢，對存儲空間要求不大，很少增加和刪除的情況。

（2）棧

棧是一種特殊的線性表，僅能在線性表的一端操作，棧頂允許操作，棧底不允許操作。 棧的特點(diǎn)是：先進(jìn)后出，或者說是后進(jìn)先出，從棧頂放入元素的操作叫入棧，取出元素叫出棧。

棧的結(jié)構(gòu)就像一個集裝箱，越先放進(jìn)去的東西越晚才能拿出來，所以，棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場景，例如斐波那契數(shù)列。

（3）隊(duì)列

隊(duì)列與棧一樣，也是一種線性表，不同的是，隊(duì)列可以在一端添加元素，在另一端取出元素，也就是：先進(jìn)先出。從一端放入元素的操作稱為入隊(duì)，取出元素為出隊(duì)，示例圖如下：

使用場景：因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)，在多線程阻塞隊(duì)列管理中非常適用。

（4）鏈表

鏈表是物理存儲單元上非連續(xù)的、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實(shí)現(xiàn)，每個元素包含兩個結(jié)點(diǎn)，一個是存儲元素的數(shù)據(jù)域 (內(nèi)存空間)，另一個是指向下一個結(jié)點(diǎn)地址的指針域。根據(jù)指針的指向，鏈表能形成不同的結(jié)構(gòu)，例如單鏈表，雙向鏈表，循環(huán)鏈表等。

鏈表的優(yōu)點(diǎn)：

鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu)，不需要初始化容量，可以任意加減元素；

添加或者刪除元素時只需要改變前后兩個元素結(jié)點(diǎn)的指針域指向地址即可，所以添加，刪除很快；

缺點(diǎn)：

因?yàn)楹写罅康闹羔樣?，占用空間較大；

查找元素需要遍歷鏈表來查找，非常耗時。

（5）樹

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做 “樹” 是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

1. 每個節(jié)點(diǎn)有零個或多個子節(jié)點(diǎn)；

2. 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

3. 每一個非根節(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)；

4. 除了根節(jié)點(diǎn)外，每個子節(jié)點(diǎn)可以分為多個不相交的子樹；

在日常的應(yīng)用中，我們討論和用的更多的是樹的其中一種結(jié)構(gòu)，就是二叉樹。

二叉樹是樹的特殊一種，具有如下特點(diǎn)：

1. 每個結(jié)點(diǎn)最多有兩顆子樹，結(jié)點(diǎn)的度最大為2。

2. 左子樹和右子樹是有順序的，次序不能顛倒。

3. 即使某結(jié)點(diǎn)只有一個子樹，也要區(qū)分左右子樹。

二叉樹是一種比較有用的折中方案，它添加，刪除元素都很快，并且在查找方面也有很多的算法優(yōu)化，所以，二叉樹既有鏈表的好處，也有數(shù)組的好處，是兩者的優(yōu)化方案，在處理大批量的動態(tài)數(shù)據(jù)方面非常有用。

擴(kuò)展：

二叉樹有很多擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，包括平衡二叉樹、紅黑樹、B+樹等，這些數(shù)據(jù)結(jié)構(gòu)二叉樹的基礎(chǔ)上衍生了很多的功能，在實(shí)際應(yīng)用中廣泛用到，例如mysql的數(shù)據(jù)庫索引結(jié)構(gòu)用的就是B+樹，還有HashMap的底層源碼中用到了紅黑樹。這些二叉樹的功能強(qiáng)大，但算法上比較復(fù)雜，想學(xué)習(xí)的話還是需要花時間去深入的。

6、散列表

散列表，也叫哈希表，是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應(yīng)元素。

記錄的存儲位置=f(key)

這里的對應(yīng)關(guān)系 f 成為散列函數(shù)，又稱為哈希 (hash函數(shù))，而散列表就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個整型數(shù)字，然后就將該數(shù)字對數(shù)組長度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲在以該數(shù)字為下標(biāo)的數(shù)組空間里，這種存儲空間可以充分利用數(shù)組的查找優(yōu)勢來查找元素，所以查找的速度很快。

哈希表在應(yīng)用中也是比較常見的，就如Java中有些集合類就是借鑒了哈希原理構(gòu)造的，例如HashMap，HashTable等，利用hash表的優(yōu)勢，對于集合的查找元素時非常方便的，然而，因?yàn)楣１硎腔跀?shù)組衍生的數(shù)據(jù)結(jié)構(gòu)，在添加刪除元素方面是比較慢的，所以很多時候需要用到一種數(shù)組鏈表來做，也就是拉鏈法。拉鏈法是數(shù)組結(jié)合鏈表的一種結(jié)構(gòu)，較早前的hashMap底層的存儲就是采用這種結(jié)構(gòu)，直到j(luò)dk1.8之后才換成了數(shù)組加紅黑樹的結(jié)構(gòu)，其示例圖如下：

從圖中可以看出，左邊很明顯是個數(shù)組，數(shù)組的每個成員包括一個指針，指向一個鏈表的頭，當(dāng)然這個鏈表可能為空，也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

哈希表的應(yīng)用場景很多，當(dāng)然也有很多問題要考慮，比如哈希沖突的問題，如果處理的不好會浪費(fèi)大量的時間，導(dǎo)致應(yīng)用崩潰。

（7）堆

堆是一種比較特殊的數(shù)據(jù)結(jié)構(gòu)，可以被看做一棵樹的數(shù)組對象，具有以下的性質(zhì)：

1. 堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

2. 堆總是一棵完全二叉樹。

將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時，稱之為堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，滿足前者的表達(dá)式的成為小頂堆，滿足后者表達(dá)式的為大頂堆，這兩者的結(jié)構(gòu)圖可以用完全二叉樹排列出來，示例圖如下：

因?yàn)槎延行虻奶攸c(diǎn)，一般用來做數(shù)組中的排序，稱為堆排序。

8、圖

圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成。其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)，邊是頂點(diǎn)的有序偶對，若兩個頂點(diǎn)之間存在一條邊，就表示這兩個頂點(diǎn)具有相鄰關(guān)系。

按照頂點(diǎn)指向的方向可分為無向圖和有向圖：

無向圖

有向圖

圖是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，在存儲數(shù)據(jù)上有著比較復(fù)雜和高效的算法，分別有鄰接矩陣 、鄰接表、十字鏈表、鄰接多重表、邊集數(shù)組等存儲結(jié)構(gòu)，這里不做展開，讀者有興趣可以自己學(xué)習(xí)深入。