1霎俩、常見數(shù)據(jù)結(jié)構(gòu)參考（https://blog.csdn.net/yeyazhishang/article/details/82353846）
2纺弊、數(shù)組
數(shù)組是可以再內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)拨与，在內(nèi)存中的分配也是連續(xù)的忆蚀，數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問根蟹，數(shù)組下標(biāo)從0開始。
int[] data = new int[100]拷肌；data[0] = 1;
優(yōu)點(diǎn)：
1到旦、按照索引查詢?cè)厮俣瓤?br>
2旨巷、按照索引遍歷數(shù)組方便
缺點(diǎn)：
1、數(shù)組的大小固定后就無法擴(kuò)容了
2添忘、數(shù)組只能存儲(chǔ)一種類型的數(shù)據(jù)
3采呐、添加，刪除的操作慢昔汉，因?yàn)橐苿?dòng)其他的元素。
適用場(chǎng)景：
頻繁查詢拴清，對(duì)存儲(chǔ)空間要求不大靶病，很少增加和刪除的情況。
3口予、棧
棧是一種特殊的線性表娄周，僅能在線性表的一端操作，棧頂允許操作沪停，棧底不允許操作煤辨。 棧的特點(diǎn)是：先進(jìn)后出，或者說是后進(jìn)先出木张，從棧頂放入元素的操作叫入棧众辨，取出元素叫出棧。
棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場(chǎng)景舷礼，例如斐波那契數(shù)列鹃彻。
4、隊(duì)列
隊(duì)列與棧一樣妻献，也是一種線性表蛛株，不同的是，隊(duì)列可以在一端添加元素育拨，在另一端取出元素谨履，也就是：先進(jìn)先出。從一端放入元素的操作稱為入隊(duì)熬丧，取出元素為出隊(duì)
因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)笋粟，在多線程阻塞隊(duì)列管理中非常適用。
5析蝴、鏈表
鏈表是物理存儲(chǔ)單元上非連續(xù)的矗钟、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實(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較大琼富；
查找元素需要遍歷鏈表來查找仪吧，非常耗時(shí)。
適用場(chǎng)景：
數(shù)據(jù)量較小鞠眉，需要頻繁增加薯鼠，刪除操作的場(chǎng)景
public class LinkedList {
private Node head; //頭節(jié)點(diǎn)
//新增節(jié)點(diǎn),在尾部新增
public void addHead(Node node) {
//頭節(jié)點(diǎn)是否存在
if (head == null) {
head = node;
return;
}
Node currentNode = head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
//新增節(jié)點(diǎn)，在頭部新增
public void addTail(Node node) {
node.next = head;
head = node;
}
//刪除下標(biāo)為k的節(jié)點(diǎn)
public boolean delete(int k) {
if (k < 0 || k > length() - 1) {
//todo 下標(biāo)越界異常處理
return false;
}
if (k == 0) {
head = head.next;
return true;
}
int j = 1;
Node currentNode = head;
Node nextNode = currentNode.next;
while (j < k) {
currentNode = currentNode.next;
nextNode = nextNode.next;
j++;
}
currentNode.next = nextNode.next;
return true;
}
//查詢下標(biāo)為k的節(jié)點(diǎn)
public Node query(int k) {
if (k < 0 || k > length() - 1) {
return null;
}
if (k == 0) {
return head;
}
Node currentNode = head;
int j = 0;
while (currentNode.next != null) {
currentNode = currentNode.next;
j++;
if (j == k) {
return currentNode;
}
}
return null;
}
//查詢鏈表長度
public int length() {
if (head == null) {
return 0;
}
int length = 1;
Node currentNode = head;
while (currentNode.next != null) {
length++;
currentNode = currentNode.next;
}
return length;
}
//遍歷節(jié)點(diǎn)
public void getAllNode() {
if (head == null) {
return;
}
Node currentNode = head;
System.out.print(head.data + ", ");
while (currentNode.next != null) {
System.out.print(currentNode.next.data + ", ");
currentNode = currentNode.next;
}
}
//在下標(biāo)為k的位置插入節(jié)點(diǎn)
public boolean insert(int k, Node node) {
if (k < 0 || k > length() - 1) {
//todo 下標(biāo)越界異常處理
return false;
}
if (k == 0) {
node.next = head;
head = node;
return true;
}
Node currentNode = head;
int i = 1;
while (i < k) {
currentNode = currentNode.next;
i++;
}
node.next = currentNode.next;
currentNode.next = node;
return true;
}
//排序節(jié)點(diǎn)
public void sort() {
if (head == null) {
return;
}
Node currentNode = head;
while (currentNode != null) {
Node nextNode = currentNode.next;
while (nextNode != null) {
if (currentNode.data > nextNode.data) {
int temp = currentNode.data;
currentNode.data = nextNode.data;
nextNode.data = temp;
}
nextNode = nextNode.next;
}
currentNode = currentNode.next;
}
}
//鏈表反轉(zhuǎn)械蹋，遍歷法 輸入原鏈表頭節(jié)點(diǎn)出皇，返回反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)(即原鏈表的尾節(jié)點(diǎn))
public Node reversal(Node head) {
if (head == null || head.next == null) return head;
Node preNode = head; //上個(gè)節(jié)點(diǎn)
Node currentNode = head.next; //當(dāng)前節(jié)點(diǎn)
Node temp; //臨時(shí)節(jié)點(diǎn)，用于保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
while (currentNode != null) { //假如當(dāng)前節(jié)點(diǎn)為null哗戈，說明此時(shí)位于尾節(jié)點(diǎn)
temp = currentNode.next;
currentNode.next = preNode; //節(jié)點(diǎn)指向反轉(zhuǎn)
//節(jié)點(diǎn)向后移動(dòng)
preNode = currentNode;
currentNode = temp;
}
head.next = null;
return preNode;
}
public static void main(String[] args) {
LinkedList ll = new LinkedList();
Node node1 = new Node(10);
Node node2 = new Node(20);
Node node3 = new Node(30);
Node node4 = new Node(40);
Node node5 = new Node(50);
Node node6 = new Node(60);
ll.addHead(node1);
ll.addHead(node2);
ll.addHead(node5);
ll.addHead(node3);
ll.addHead(node6);
ll.addHead(node4);
System.out.print("排序前：");
ll.getAllNode();
ll.sort();
System.out.print("\n排序后：");
ll.getAllNode();
System.out.println("\n鏈表長度=" + ll.length());
ll.delete(2);
System.out.print("\n刪除下標(biāo)為2的節(jié)點(diǎn)：");
ll.getAllNode();
System.out.println("\n刪除后長度=" + ll.length());
System.out.println("\n下標(biāo)為0的節(jié)點(diǎn)=" + ll.query(0).data);
Node reversal = ll.reversal(node1);
//遍歷反轉(zhuǎn)后的鏈表
System.out.print("\n 反轉(zhuǎn)后的鏈表：" +reversal.data + ", ");
while (reversal.next != null) {
reversal = reversal.next;
System.out.print(reversal.data + ", ");
}
}
}
6恶迈、樹
樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合谱醇。把它叫做 “樹” 是因?yàn)樗雌饋硐褚豢玫箳斓臉湎局伲簿褪钦f它是根朝上，而葉朝下的副渴。它具有以下的特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)奈附；
- 沒有父節(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è)不相交的子樹；
6.2 樹的分類：
-
平衡二叉樹
它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1勉盅，并且左右兩個(gè)子樹都是一棵平衡二叉樹佑颇。
image.png
二叉樹遍歷：
a. 前序遍歷，根左右
b. 中序遍歷草娜，左根右
c. 后序遍歷挑胸，左右根
前序：abdefgc
中序：debgfac
后序：edgfbca
//前序遍歷
public void preOrderTraverse(DataNode node){
if (node==null) {
return;
}
System.out.print(node.data);
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
//中序遍歷
public void inOrderTraverse(DataNode node){
if (node==null) {
return;
}
inOrderTraverse(node.leftChild);
System.out.print(node.data);
inOrderTraverse(node.rightChild);
}
//后序遍歷
public void postOrderTraverse(DataNode node){
if (node==null) {
return;
}
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data);
}
-
二叉搜索樹
若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值宰闰，若它的右子樹不空茬贵，則右子樹上所有結(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值簿透。對(duì)它進(jìn)行中序遍歷得到的是有序的數(shù)組。
image.png -
紅黑樹 參考
自平衡的二叉查找樹解藻，紅黑樹也屬于平衡二叉樹老充。
性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色螟左。
性質(zhì)2：根節(jié)點(diǎn)是黑色啡浊。
性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。
性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色胶背。
性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)巷嚣。
一棵n個(gè)結(jié)點(diǎn)的紅黑樹始終保持了logn的高度，所以紅黑樹的查找奄妨、插入涂籽、刪除的時(shí)間復(fù)雜度最壞為O(log n)苹祟。
image.png
左旋
右旋 -
B樹 參考
B樹屬于多叉樹又名平衡多路查找樹
每個(gè)節(jié)點(diǎn)都存儲(chǔ)Key和data砸抛，所有的節(jié)點(diǎn)組成這棵樹，并且葉子節(jié)點(diǎn)指針為null树枫。
image.png
一個(gè)m階的B樹具有如下幾個(gè)特征：
- 根結(jié)點(diǎn)至少有兩個(gè)子女直焙。
- 每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子，其中 m/2 <= k <= m
- 每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素砂轻，其中 m/2 <= k <= m
- 所有的葉子結(jié)點(diǎn)都位于同一層奔誓。
- 每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃搔涝。
- B+樹 參考
只有葉子節(jié)點(diǎn)存儲(chǔ)data厨喂，葉子節(jié)點(diǎn)包含了這棵樹的所有鍵值，葉子節(jié)點(diǎn)不存儲(chǔ)指針庄呈，后來加上了順序訪問指針蜕煌。
一個(gè)m階的B+樹具有如下幾個(gè)特征：
- 有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)诬留，只用來索引斜纪，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
- 所有的葉子結(jié)點(diǎn)中包含了全部元素的信息文兑，及指向含這些元素記錄的指針盒刚，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
- 所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)绿贞，在子節(jié)點(diǎn)元素中是最大（或最幸蚩椤）元素。
B樹和B+樹的區(qū)別：
B樹中關(guān)鍵字分布在整個(gè)樹中籍铁，葉節(jié)點(diǎn)不包含任何關(guān)鍵信息贮聂，B+樹的關(guān)鍵信息在葉子節(jié)點(diǎn)中靠柑，非葉子節(jié)點(diǎn)只存儲(chǔ)索引；B樹的關(guān)鍵字只存在一個(gè)節(jié)點(diǎn)中吓懈，B+樹的關(guān)鍵字必須在葉子節(jié)點(diǎn)歼冰，非葉子節(jié)點(diǎn)可能存在。
7耻警、散列表
散列表隔嫡，也叫哈希表，是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)甘穿，通過key和value來映射到集合中的一個(gè)位置腮恩，這樣就可以很快找到集合中的對(duì)應(yīng)元素。
記錄的存儲(chǔ)位置=f(key)
這里的對(duì)應(yīng)關(guān)系 f 成為散列函數(shù)温兼，又稱為哈希 (hash函數(shù))秸滴，而散列表就是把Key通過一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長度進(jìn)行取余募判，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)荡含，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里，這種存儲(chǔ)空間可以充分利用數(shù)組的查找優(yōu)勢(shì)來查找元素届垫，所以查找的速度很快释液。
8、堆
堆是一種比較特殊的數(shù)據(jù)結(jié)構(gòu)装处，可以被看做一棵樹的數(shù)組對(duì)象误债，具有以下的性質(zhì)：
- 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
-
堆總是一棵完全二叉樹妄迁。
image.png
一般升序采用大頂堆寝蹈，降序采用小頂堆。
9登淘、圖
圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成箫老。其中，為了與樹形結(jié)構(gòu)加以區(qū)別形帮，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)槽惫，邊是頂點(diǎn)的有序偶對(duì)，若兩個(gè)頂點(diǎn)之間存在一條邊辩撑，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系界斜。
圖在代碼里主要通過鄰接列表和鄰接矩陣來實(shí)現(xiàn)。
深度優(yōu)先算法和廣度優(yōu)先算法參考
-
深度優(yōu)先算法DFS
沿著圖的深度遍歷圖的節(jié)點(diǎn)合冀，盡可能深的搜索圖的分支各薇。 當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。 這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止峭判。
步驟：
- 從最開始的節(jié)點(diǎn)A開始开缎，獲取與它相鄰的節(jié)點(diǎn)B
- 判斷這個(gè)節(jié)點(diǎn)是否被訪問過，如果訪問過林螃，那么就不再重復(fù)訪問奕删，如果沒有則進(jìn)行下一步
- 已當(dāng)前的節(jié)點(diǎn)B為當(dāng)前節(jié)點(diǎn)，進(jìn)行深度優(yōu)先搜索算法
3.1. 將當(dāng)前節(jié)點(diǎn)的訪問狀態(tài)設(shè)為已訪問
3.2. 獲取當(dāng)前節(jié)點(diǎn)的下一個(gè)相鄰節(jié)點(diǎn)C
3.3. 判斷相鄰節(jié)點(diǎn)C是否是終止節(jié)點(diǎn)疗认，如果是終止節(jié)點(diǎn)完残，那么算法結(jié)束
3.4. 判斷當(dāng)前節(jié)點(diǎn)是否被訪問過，如果沒有被訪問過横漏，那么重復(fù)將訪問狀態(tài)設(shè)為已訪問谨设，如果訪問過了，
那么獲取下一個(gè)相鄰節(jié)點(diǎn)缎浇，然后重復(fù)3.1至3.4
-
廣度優(yōu)先算法BFS
從根節(jié)點(diǎn)開始扎拣，沿著圖的寬度遍歷圖的節(jié)點(diǎn)。
步驟：
- 從最開始的節(jié)點(diǎn)A開始素跺，獲取與它相鄰的所有節(jié)點(diǎn)B二蓝，C等，如果元素沒有被訪問過就加入隊(duì)列
- 從隊(duì)列獲取之前加入的元素B作為當(dāng)前元素亡笑，獲取與它相鄰的元素D侣夷，E等横朋，如果元素是終點(diǎn)就結(jié)束仑乌，如果元素沒有被訪問過就加入隊(duì)列
- 重復(fù)步驟2直到找到終點(diǎn)
