數據結構分類

數據結構是指相互之間存在著一種或多種關(guan) 係的數據元素的集合和該集合中數據元素之間的關(guan) 係組成 。
常用的數據結構有：數組，棧，鏈表，隊列，樹，圖，堆，散列表等，如圖所示： 
 
每一種數據結構都有著獨特的數據存儲(chu) 方式，下麵為(wei) 大家介紹它們(men) 的結構和優(you) 缺點。

1、數組

數組是可以再內(nei) 存中連續存儲(chu) 多個(ge) 元素的結構，在內(nei) 存中的分配也是連續的，數組中的元素通過數組下標進行訪問，數組下標從(cong) 0開始。例如下麵這段代碼就是將數組的第一個(ge) 元素賦值為(wei) 1。

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

優(you) 點：
1、按照索引查詢元素速度快
2、按照索引遍曆數組方便

缺點：
1、數組的大小固定後就無法擴容了
2、數組隻能存儲(chu) 一種類型的數據
3、添加，刪除的操作慢，因為(wei) 要移動其他的元素。

適用場景：
頻繁查詢，對存儲(chu) 空間要求不大，很少增加和刪除的情況。

2、棧

棧是一種特殊的線性表，僅(jin) 能在線性表的一端操作，棧頂允許操作，棧底不允許操作。 棧的特點是：先進後出，或者說是後進先出，從(cong) 棧頂放入元素的操作叫入棧，取出元素叫出棧。 
 
棧的結構就像一個(ge) 集裝箱，越先放進去的東(dong) 西越晚才能拿出來，所以，棧常應用於(yu) 實現遞歸功能方麵的場景，例如斐波那契數列。

3、隊列

隊列與(yu) 棧一樣，也是一種線性表，不同的是，隊列可以在一端添加元素，在另一端取出元素，也就是：先進先出。從(cong) 一端放入元素的操作稱為(wei) 入隊，取出元素為(wei) 出隊，示例圖如下： 
 
使用場景：因為(wei) 隊列先進先出的特點，在多線程阻塞隊列管理中非常適用。

4、鏈表

鏈表是物理存儲(chu) 單元上非連續的、非順序的存儲(chu) 結構，數據元素的邏輯順序是通過鏈表的指針地址實現，每個(ge) 元素包含兩(liang) 個(ge) 結點，一個(ge) 是存儲(chu) 元素的數據域 (內(nei) 存空間)，另一個(ge) 是指向下一個(ge) 結點地址的指針域。根據指針的指向，鏈表能形成不同的結構，例如單鏈表，雙向鏈表，循環鏈表等。 
 
鏈表的優(you) 點：
鏈表是很常用的一種數據結構，不需要初始化容量，可以任意加減元素；
添加或者刪除元素時隻需要改變前後兩(liang) 個(ge) 元素結點的指針域指向地址即可，所以添加，刪除很快；

缺點：
因為(wei) 含有大量的指針域，占用空間較大；
查找元素需要遍曆鏈表來查找，非常耗時。

適用場景：
數據量較小，需要頻繁增加，刪除操作的場景

5、樹

樹是一種數據結構，它是由n（n>=1）個(ge) 有限節點組成一個(ge) 具有層次關(guan) 係的集合。把它叫做 “樹” 是因為(wei) 它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

• 每個節點有零個或多個子節點；
• 沒有父節點的節點稱為根節點；
• 每一個非根節點有且隻有一個父節點；
• 除了根節點外，每個子節點可以分為多個不相交的子樹；

在日常的應用中，我們(men) 討論和用的更多的是樹的其中一種結構，就是二叉樹。 
 
二叉樹是樹的特殊一種，具有如下特點：

1、每個(ge) 結點最多有兩(liang) 顆子樹，結點的度最大為(wei) 2。
2、左子樹和右子樹是有順序的，次序不能顛倒。
3、即使某結點隻有一個(ge) 子樹，也要區分左右子樹。

二叉樹是一種比較有用的折中方案，它添加，刪除元素都很快，並且在查找方麵也有很多的算法優(you) 化，所以，二叉樹既有鏈表的好處，也有數組的好處，是兩(liang) 者的優(you) 化方案，在處理大批量的動態數據方麵非常有用。

擴展：
二叉樹有很多擴展的數據結構，包括平衡二叉樹、紅黑樹、B+樹等，這些數據結構二叉樹的基礎上衍生了很多的功能，在實際應用中廣泛用到，例如mysql的數據庫索引結構用的就是B+樹，還有HashMap的底層源碼中用到了紅黑樹。這些二叉樹的功能強大，但算法上比較複雜，想學習(xi) 的話還是需要花時間去深入的。

6、散列表

散列表，也叫哈希表，是根據關(guan) 鍵碼和值 (key和value) 直接進行訪問的數據結構，通過key和value來映射到集合中的一個(ge) 位置，這樣就可以很快找到集合中的對應元素。

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

這裏的對應關(guan) 係 f 成為(wei) 散列函數，又稱為(wei) 哈希 (hash函數)，而散列表就是把Key通過一個(ge) 固定的算法函數既所謂的哈希函數轉換成一個(ge) 整型數字，然後就將該數字對數組長度進行取餘(yu) ，取餘(yu) 結果就當作數組的下標，將value存儲(chu) 在以該數字為(wei) 下標的數組空間裏，這種存儲(chu) 空間可以充分利用數組的查找優(you) 勢來查找元素，所以查找的速度很快。

哈希表在應用中也是比較常見的，就如Java中有些集合類就是借鑒了哈希原理構造的，例如HashMap，HashTable等，利用hash表的優(you) 勢，對於(yu) 集合的查找元素時非常方便的，然而，因為(wei) 哈希表是基於(yu) 數組衍生的數據結構，在添加刪除元素方麵是比較慢的，所以很多時候需要用到一種數組鏈表來做，也就是拉鏈法。拉鏈法是數組結合鏈表的一種結構，較早前的hashMap底層的存儲(chu) 就是采用這種結構，直到jdk1.8之後才換成了數組加紅黑樹的結構，其示例圖如下： 
 
從(cong) 圖中可以看出，左邊很明顯是個(ge) 數組，數組的每個(ge) 成員包括一個(ge) 指針，指向一個(ge) 鏈表的頭，當然這個(ge) 鏈表可能為(wei) 空，也可能元素很多。我們(men) 根據元素的一些特征把元素分配到不同的鏈表中去，也是根據這些特征，找到正確的鏈表，再從(cong) 鏈表中找出這個(ge) 元素。

哈希表的應用場景很多，當然也有很多問題要考慮，比如哈希衝(chong) 突的問題，如果處理的不好會(hui) 浪費大量的時間，導致應用崩潰。

7、堆

堆是一種比較特殊的數據結構，可以被看做一棵樹的數組對象，具有以下的性質：

• 堆中某個(ge) 節點的值總是不大於(yu) 或不小於(yu) 其父節點的值；

• 堆總是一棵完全二叉樹。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

堆的定義(yi) 如下：n個(ge) 元素的序列{k1,k2,ki,…,kn}當且僅(jin) 當滿足下關(guan) 係時，稱之為(wei) 堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，滿足前者的表達式的成為(wei) 小頂堆，滿足後者表達式的為(wei) 大頂堆，這兩(liang) 者的結構圖可以用完全二叉樹排列出來，示例圖如下： 
 
因為(wei) 堆有序的特點，一般用來做數組中的排序，稱為(wei) 堆排序。

8、圖

圖是由結點的有窮集合V和邊的集合E組成。其中，為(wei) 了與(yu) 樹形結構加以區別，在圖結構中常常將結點稱為(wei) 頂點，邊是頂點的有序偶對，若兩(liang) 個(ge) 頂點之間存在一條邊，就表示這兩(liang) 個(ge) 頂點具有相鄰關(guan) 係。

按照頂點指向的方向可分為(wei) 無向圖和有向圖： 
  
 
圖是一種比較複雜的數據結構，在存儲(chu) 數據上有著比較複雜和高效的算法，分別有鄰接矩陣 、鄰接表、十字鏈表、鄰接多重表、邊集數組等存儲(chu) 結構，這裏不做展開，讀者有興(xing) 趣可以自己學習(xi) 深入。