數(shù)據(jù)結(jié)構(gòu)分類(lèi)
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成 。
常用的數(shù)據(jù)結(jié)構(gòu)有：
- 數(shù)組（Array）
- 棧（Stack）
- 鏈表（Linked List）
- 隊(duì)列（Queue）
- 樹(shù)（Tree）
- 圖（Graph）
- 堆（Heap）
- 散列表（Hash）
等挺益。每一種數(shù)據(jù)結(jié)構(gòu)都有著獨(dú)特的數(shù)據(jù)存儲(chǔ)方式，
1、數(shù)組
數(shù)組是可以再內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)渔工，在內(nèi)存中的分配也是連續(xù)的畦贸，數(shù)組中的元素通過(guò)數(shù)組下標(biāo)進(jìn)行訪問(wèn)，數(shù)組下標(biāo)從0開(kāi)始樟凄。
優(yōu)點(diǎn)：
1聘芜、按照索引查詢?cè)厮俣瓤?br>
2、按照索引遍歷數(shù)組方便
缺點(diǎn)：
1缝龄、數(shù)組的大小固定后就無(wú)法擴(kuò)容了
2汰现、數(shù)組只能存儲(chǔ)一種類(lèi)型的數(shù)據(jù)
3、添加叔壤，刪除的操作慢瞎饲，因?yàn)橐苿?dòng)其他的元素。
適用場(chǎng)景：
頻繁查詢炼绘，對(duì)存儲(chǔ)空間要求不大嗅战，很少增加和刪除的情況。
2俺亮、棧
棧是一種特殊的線性表驮捍，僅能在線性表的一端操作，棧頂允許操作铅辞，棧底不允許操作厌漂。
特點(diǎn)：
先進(jìn)后出，或者說(shuō)是后進(jìn)先出斟珊，從棧頂放入元素的操作叫入棧苇倡，取出元素叫出棧富纸。
棧的結(jié)構(gòu)就像一個(gè)集裝箱，越先放進(jìn)去的東西越晚才能拿出來(lái)旨椒。
適用場(chǎng)景：
棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場(chǎng)景晓褪，例如瀏覽器push。
3综慎、隊(duì)列
隊(duì)列與棧一樣涣仿，也是一種線性表，不同的是示惊，隊(duì)列可以在一端添加元素好港，在另一端取出元素。
特點(diǎn)：
先進(jìn)先出米罚。從一端放入元素的操作稱為入隊(duì)钧汹，取出元素為出隊(duì)，示例圖如下：
使用場(chǎng)景：
因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)录择，在多線程阻塞隊(duì)列管理中非常適用拔莱。
4、鏈表
鏈表是物理存儲(chǔ)單元上非連續(xù)的隘竭、非順序的存儲(chǔ)結(jié)構(gòu)塘秦，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表的指針地址實(shí)現(xiàn)，每個(gè)元素包含兩個(gè)結(jié)點(diǎn)动看，一個(gè)是存儲(chǔ)元素的數(shù)據(jù)域 (內(nèi)存空間)尊剔，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)地址的指針域。根據(jù)指針的指向弧圆，鏈表能形成不同的結(jié)構(gòu)赋兵，例如單鏈表，雙向鏈表搔预，循環(huán)鏈表等霹期。
鏈表的優(yōu)點(diǎn)：
鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu)，不需要初始化容量拯田，可以任意加減元素历造；
添加或者刪除元素時(shí)只需要改變前后兩個(gè)元素結(jié)點(diǎn)的指針域指向地址即可，所以添加船庇，刪除很快吭产；
缺點(diǎn)：
因?yàn)楹写罅康闹羔樣颍加每臻g較大鸭轮；
查找元素需要遍歷鏈表來(lái)查找臣淤，非常耗時(shí)。
適用場(chǎng)景：（數(shù)據(jù)量較小窃爷，需要頻繁增加邑蒋，刪除操作的場(chǎng)景姓蜂。）：
- 結(jié)合哈希表：LRU 緩存、鏈地址法解決哈希沖突医吊。
- 循環(huán)鏈表：約瑟夫問(wèn)題
5钱慢、樹(shù)
樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合卿堂。把它叫做 “樹(shù)” 是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)束莫，也就是說(shuō)它是根朝上，而葉朝下的草描。
特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)览绿；
- 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
- 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)陶珠；
- 除了根節(jié)點(diǎn)外挟裂，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)；
在日常的應(yīng)用中揍诽，我們討論和用的更多的是樹(shù)的其中一種結(jié)構(gòu)，就是二叉樹(shù)栗竖。
二叉樹(shù)特點(diǎn)：
1暑脆、每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)，結(jié)點(diǎn)的度最大為2狐肢。
2添吗、左子樹(shù)和右子樹(shù)是有順序的，次序不能顛倒份名。
3碟联、即使某結(jié)點(diǎn)只有一個(gè)子樹(shù)，也要區(qū)分左右子樹(shù)僵腺。
二叉樹(shù)是一種比較有用的折中方案鲤孵，它添加贺喝，刪除元素都很快舍沙，并且在查找方面也有很多的算法優(yōu)化，所以糟港，二叉樹(shù)既有鏈表的好處琉兜，也有數(shù)組的好處凯正，是兩者的優(yōu)化方案，在處理大批量的動(dòng)態(tài)數(shù)據(jù)方面非常有用豌蟋。
擴(kuò)展：
二叉樹(shù)有很多擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)廊散，包括平衡二叉樹(shù)、紅黑樹(shù)梧疲、B+樹(shù)等允睹。
6施符、散列表
散列表，也叫哈希表擂找，是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)戳吝，通過(guò)key和value來(lái)映射到集合中的一個(gè)位置，這樣就可以很快找到集合中的對(duì)應(yīng)元素贯涎。
記錄的存儲(chǔ)位置=f(key)
這里的對(duì)應(yīng)關(guān)系 f 成為散列函數(shù)听哭，又稱為哈希 (hash函數(shù))，而散列表就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字塘雳，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余陆盘，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里败明，這種存儲(chǔ)空間可以充分利用數(shù)組的查找優(yōu)勢(shì)來(lái)查找元素隘马，所以查找的速度很快。
哈希表在應(yīng)用中也是比較常見(jiàn)的妻顶，就如Java中有些集合類(lèi)就是借鑒了哈希原理構(gòu)造的酸员，例如HashMap，HashTable等讳嘱，利用hash表的優(yōu)勢(shì)幔嗦，對(duì)于集合的查找元素時(shí)非常方便的，然而沥潭，因?yàn)楣１硎腔跀?shù)組衍生的數(shù)據(jù)結(jié)構(gòu)邀泉，在添加刪除元素方面是比較慢的，所以很多時(shí)候需要用到一種數(shù)組鏈表來(lái)做钝鸽，也就是拉鏈法汇恤。拉鏈法是數(shù)組結(jié)合鏈表的一種結(jié)構(gòu)，較早前的hashMap底層的存儲(chǔ)就是采用這種結(jié)構(gòu)拔恰，直到j(luò)dk1.8之后才換成了數(shù)組加紅黑樹(shù)的結(jié)構(gòu)因谎，其示例圖如下：
從圖中可以看出，左邊很明顯是個(gè)數(shù)組仁连，數(shù)組的每個(gè)成員包括一個(gè)指針蓝角，指向一個(gè)鏈表的頭，當(dāng)然這個(gè)鏈表可能為空饭冬，也可能元素很多使鹅。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征昌抠，找到正確的鏈表患朱，再?gòu)逆湵碇姓页鲞@個(gè)元素。
哈希表的應(yīng)用場(chǎng)景很多炊苫，當(dāng)然也有很多問(wèn)題要考慮裁厅，比如哈希沖突的問(wèn)題冰沙，如果處理的不好會(huì)浪費(fèi)大量的時(shí)間，導(dǎo)致應(yīng)用崩潰执虹。
7拓挥、堆
堆是一種比較特殊的數(shù)據(jù)結(jié)構(gòu)，可以被看做一棵樹(shù)的數(shù)組對(duì)象袋励。
特點(diǎn)：
- 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值侥啤；
- 堆總是一棵完全二叉樹(shù)。
將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆茬故，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆盖灸。常見(jiàn)的堆有二叉堆、斐波那契堆等磺芭。
堆的定義如下：
n個(gè)元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)赁炎，稱之為堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)钾腺，滿足前者的表達(dá)式的成為小頂堆徙垫，滿足后者表達(dá)式的為大頂堆，這兩者的結(jié)構(gòu)圖可以用完全二叉樹(shù)排列出來(lái)垮庐，示例圖如下：
因?yàn)槎延行虻奶攸c(diǎn)松邪，一般用來(lái)做數(shù)組中的排序，稱為堆排序哨查。
8、圖
圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成剧辐。其中寒亥，為了與樹(shù)形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)荧关，邊是頂點(diǎn)的有序偶對(duì)溉奕，若兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系忍啤。
按照頂點(diǎn)指向的方向可分為有向圖和無(wú)向圖：
圖是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)加勤，在存儲(chǔ)數(shù)據(jù)上有著比較復(fù)雜和高效的算法，分別有鄰接矩陣 同波、鄰接表鳄梅、十字鏈表、鄰接多重表未檩、邊集數(shù)組等存儲(chǔ)結(jié)構(gòu)戴尸，這里不做展開(kāi)，讀者有興趣可以自己學(xué)習(xí)深入冤狡。
