數(shù)據(jù)結構分類

數(shù)據(jù)結構是指相互之間存在著一種或多種關系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關系組成 本昏。

常用的數(shù)據(jù)結構有：數(shù)組，棧枪汪，鏈表涌穆，隊列，樹雀久，圖宿稀，堆，散列表等赖捌，如圖所示：

image.png

每一種數(shù)據(jù)結構都有著獨特的數(shù)據(jù)存儲方式祝沸，下面介紹它們的結構和優(yōu)缺點。

1、數(shù)組

數(shù)組是可以再內存中連續(xù)存儲多個元素的結構罩锐，在內存中的分配也是連續(xù)的枫攀，數(shù)組中的元素通過數(shù)組下標進行訪問诫欠，數(shù)組下標從0開始。例如下面這段代碼就是將數(shù)組的第一個元素賦值為 1。

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

優(yōu)點：

1. 按照索引查詢元素速度快
2. 按照索引遍歷數(shù)組方便

缺點：

1. 數(shù)組的大小固定后就無法擴容了
2. 數(shù)組只能存儲一種類型的數(shù)據(jù)
3. 添加，刪除的操作慢脉顿，因為要移動其他的元素车要。

適用場景：

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

2、棧

棧是一種特殊的線性表寿桨，僅能在線性表的一端操作此衅，棧頂允許操作，棧底不允許操作亭螟。 棧的特點是：先進后出挡鞍，或者說是后進先出，從棧頂放入元素的操作叫入棧预烙，取出元素叫出棧墨微。示例圖如下：

image.png

棧的結構就像一個集裝箱，越先放進去的東西越晚才能拿出來扁掸，所以翘县，棧常應用于實現(xiàn)遞歸功能方面的場景，例如斐波那契數(shù)列谴分。

3锈麸、隊列

隊列與棧一樣，也是一種線性表牺蹄，不同的是忘伞，隊列可以在一端添加元素，在另一端取出元素沙兰，也就是：先進先出氓奈。從一端放入元素的操作稱為入隊，取出元素為出隊鼎天，示例圖如下：

image.png

使用場景：

因為隊列先進先出的特點舀奶，在多線程阻塞隊列管理中非常適用。

4训措、鏈表

鏈表是物理存儲單元上非連續(xù)的伪节、非順序的存儲結構光羞，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實現(xiàn)，每個元素包含兩個結點怀大，一個是存儲元素的數(shù)據(jù)域 (內存空間)纱兑，另一個是指向下一個結點地址的指針域。根據(jù)指針的指向化借，鏈表能形成不同的結構潜慎，例如單鏈表，雙向鏈表蓖康，循環(huán)鏈表等铐炫。示例圖如下：

image.png

優(yōu)點：

1. 鏈表是很常用的一種數(shù)據(jù)結構，不需要初始化容量蒜焊，可以任意加減元素倒信；
2. 添加或者刪除元素時只需要改變前后兩個元素結點的指針域指向地址即可，所以添加泳梆，刪除很快鳖悠；

缺點：

1. 因為含有大量的指針域，占用空間較大优妙；
2. 查找元素需要遍歷鏈表來查找乘综，非常耗時。

適用場景：

數(shù)據(jù)量較小套硼，需要頻繁增加卡辰，刪除操作的場景

5、樹

樹是一種數(shù)據(jù)結構邪意，它是由n（n>=1）個有限節(jié)點組成一個具有層次關系的集合九妈。把它叫做 “樹” 是因為它看起來像一棵倒掛的樹，也就是說它是根朝上雾鬼，而葉朝下的允蚣。

特點：

1. 每個節(jié)點有零個或多個子節(jié)點；
2. 沒有父節(jié)點的節(jié)點稱為根節(jié)點呆贿；
3. 每一個非根節(jié)點有且只有一個父節(jié)點；
4. 除了根節(jié)點外森渐，每個子節(jié)點可以分為多個不相交的子樹做入；

在日常的應用中，我們討論和用的更多的是樹的其中一種結構同衣，就是二叉樹竟块。示例圖如下：

image.png

二叉樹是樹的特殊一種，具有如下特點：

1. 每個結點最多有兩顆子樹耐齐，結點的度最大為2浪秘。
2. 左子樹和右子樹是有順序的蒋情，次序不能顛倒。
3. 即使某結點只有一個子樹耸携，也要區(qū)分左右子樹棵癣。

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

擴展：

二叉樹有很多擴展的數(shù)據(jù)結構，包括平衡二叉樹颊咬、紅黑樹务甥、B+樹等，這些數(shù)據(jù)結構二叉樹的基礎上衍生了很多的功能贪染，在實際應用中廣泛用到缓呛，例如mysql的數(shù)據(jù)庫索引結構用的就是B+樹，還有HashMap的底層源碼中用到了紅黑樹杭隙。這些二叉樹的功能強大哟绊，但算法上比較復雜，想學習的話還是需要花時間去深入的痰憎。

6票髓、散列表

散列表，也叫哈希表铣耘，是根據(jù)關鍵碼和值 (key和value) 直接進行訪問的數(shù)據(jù)結構洽沟，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應元素蜗细。記錄的存儲位置=f(key)

這里的對應關系 f 成為散列函數(shù)裆操，又稱為哈希 (hash函數(shù))，而散列表就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉換成一個整型數(shù)字炉媒，然后就將該數(shù)字對數(shù)組長度進行取余踪区，取余結果就當作數(shù)組的下標，將value存儲在以該數(shù)字為下標的數(shù)組空間里吊骤，這種存儲空間可以充分利用數(shù)組的查找優(yōu)勢來查找元素缎岗，所以查找的速度很快。

應用：

哈希表在應用中也是比較常見的白粉，就如Java中有些集合類就是借鑒了哈希原理構造的传泊，例如HashMap鼠渺，HashTable等，利用hash表的優(yōu)勢眷细，對于集合的查找元素時非常方便的拦盹，然而，因為哈希表是基于數(shù)組衍生的數(shù)據(jù)結構薪鹦，在添加刪除元素方面是比較慢的掌敬，所以很多時候需要用到一種數(shù)組鏈表來做，也就是拉鏈法池磁。拉鏈法是數(shù)組結合鏈表的一種結構奔害，較早前的hashMap底層的存儲就是采用這種結構，直到jdk1.8之后才換成了數(shù)組加紅黑樹的結構地熄，其示例圖如下：

image.png

解釋：

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

哈希表的應用場景很多，當然也有很多問題要考慮闽晦，比如哈希沖突的問題扳碍，如果處理的不好會浪費大量的時間，導致應用崩潰仙蛉。

7笋敞、堆

堆是一種比較特殊的數(shù)據(jù)結構，可以被看做一棵樹的數(shù)組對象荠瘪。

具有以下的性質：

1. 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值夯巷；
2. 堆總是一棵完全二叉樹。
3. 將根節(jié)點最大的堆叫做最大堆或大根堆哀墓，根節(jié)點最小的堆叫做最小堆或小根堆鞭莽。常見的堆有二叉堆、斐波那契堆等麸祷。

堆的定義如下：

n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆褒搔。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)阶牍，滿足前者的表達式的成為小頂堆喷面，滿足后者表達式的為大頂堆，這兩者的結構圖可以用完全二叉樹排列出來走孽，示例圖如下：

image.png

因為堆有序的特點惧辈，一般用來做數(shù)組中的排序，稱為堆排序磕瓷。

8盒齿、圖

圖是由結點的有窮集合V和邊的集合E組成。其中困食，為了與樹形結構加以區(qū)別边翁，在圖結構中常常將結點稱為頂點，邊是頂點的有序偶對硕盹，若兩個頂點之間存在一條邊符匾，就表示這兩個頂點具有相鄰關系。

按照頂點指向的方向可分為無向圖和有向圖瘩例，示例圖如下：

image.png

圖是一種比較復雜的數(shù)據(jù)結構啊胶，在存儲數(shù)據(jù)上有著比較復雜和高效的算法，分別有鄰接矩陣 垛贤、鄰接表焰坪、十字鏈表、鄰接多重表聘惦、邊集數(shù)組等存儲結構某饰，這里不做展開，讀者有興趣可以自己學習深入部凑。

參考：

https://blog.csdn.net/yeyazhishang/article/details/82353846