一、數據結構概述

1.1 概念

在計算機科學中，數據結構是一種數據組織、管理和存儲的格式 。它是相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術相關。

1.1.1 數據邏輯結構

數據的邏輯結構是指數據元素之間存在的邏輯關系，由數據元素的集合和定義在此集合上的關系組成。數據的邏輯結構與數據的存儲無關，獨立于計算機，是從具體問題抽象出來的數學模型。

數據的邏輯結構由兩個要素構成，分別是：數據元素的集合和關系的集合 。

1.1.2 數據存儲結構

數據的邏輯結構在計算機中的存儲表示或實現叫做數據的存儲結構，也叫物理結構。數據的存儲結構依賴于計算機。

一般來說，一種數據結構的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序存儲、鏈式存儲、索引存儲和哈希存儲等。

數據的順序存儲結構的特點是：借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；非順序存儲的特點是：借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。

1.1.3 數據的運算

數據操作是指對數據結構中的數據元素進行運算或處理。數據操作定義在數據的邏輯結構上，每種邏輯結構都需要一組對其數據元素進行處理以實現特定功能的操作，如插入、刪除、更新等。數據操作的實現依賴于數據的存儲結構。

數據的運算包括：檢索、排序、插入、刪除、修改等。

二、常見的數據結構

常見的數據結構有：數組(Array)、棧(Stack)、隊列(Queue)、鏈表(Linked List)、樹(Tree)、圖(Graph)、堆(Heap)、散列表(Hash)。

2.1 數組(Array)

數組是一種線性結構，是可以在內存中連續存儲多個元素的結構，在內存中的分配也是連續的，數組中的元素通過數組下標進行訪問，數組下標從0開始。

• 優點：訪問數據簡單。
• 缺點：添加和刪除數據比較耗時間，因為要移動其他的元素；數組只能存儲一種類型的數據；數組的大小固定后就無法擴容了
• 使用場景：頻繁查詢，對存儲空間要求不大，很少增加和刪除的情況。

int[] a = {1,3,4,5,6,8,9,26,30,89};//直接創建并聲明容量元素的數組int[] data = new int[100]；// 創建一個整型int數組，大小是100個data[0]  = 1;  // 向數組第一個元素賦值1；
data[1]  = 2;  // 向數組第二個元素賦值2；

JDK提供的順序表有：java.util.ArrayList 其底層實現就是數組

數組（順序表）時間復雜度分析：

1. 查詢get(i) ，不難看出不論數據元素量N有多大，只需要一次eles[i] 就可以獲取到對應的元素，所以時間復雜度為O(1)
2. 插入insert(int i, T t)，每一次插入，都需要把i位置后面的元素移動一次，隨著元素數量N的增大，移動的元素也越多，時間復雜度為O(n)
3. 刪除元素remove(int i)，每一次刪除，都需要把i位置后面的元素移動一次，隨著數據量N的增大，移動的元素也越多，時間復雜度為O(n)
4. 數組長度是固定的，所以在操作的過程中涉及到了容器擴容操作。這樣會導致順序表在使用過程中的時間復雜度不是線性的，在某些擴容的結點處，耗時會突增，尤其是元素越多，這個問題越明顯

2.2 鏈表(Linked List)

鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構，這種存儲結構具有在物理上非連續、非順序的特點。鏈表由一系列數據結點構成，每個數據結點包括數據域和指針域兩部分。其中，指針域保存了數據結構中下一個元素存放的地址。

鏈表結構中數據元素的邏輯順序通過鏈表中的指針鏈接次序實現 。

根據指針的指向，鏈表能形成不同的結構，例如單鏈表，雙向鏈表，循環鏈表等。

鏈表時間復雜度分析：

1. get(int i)：每一次查詢，都需要從鏈表的頭部開始，依次向后查找，隨著數據元素N的增多，比較的元素越多，時間復雜度為O(n)
2. insert(int i, T t)：每一次插入，需要先找到i位置的前一個元素，然后完成插入操作，隨著數據元素N的增多，查找的元素越多，時間復雜度為O(n)
3. remove(int i)：每一次移除，需要先找到i位置的前一個元素，然后完成插入操作，隨著數據元素N的增多，查找的元素越多，時間復雜度為O(n)

ArrayList vs LinkedList

ArrayList

1. 基于數組，需要連續內存
2. 隨機訪問快（指根據下標訪問）
3. 尾部插入、刪除性能可以，其它部分插入、刪除都會移動數據，因此性能會低
4. 可以利用 cpu 緩存，局部性原理

LinkedList

1. 基于雙向鏈表，無需連續內存
2. 隨機訪問慢（要沿著鏈表遍歷）
3. 頭尾插入刪除性能高
4. 占用內存多

鏈表的優點：?

• 鏈表是很常用的一種數據結構，不需要初始化容量，可以任意加減元素；?
• 添加或者刪除元素時只需要改變前后兩個元素結點的指針域指向地址即可，所以添加，刪除很快；

缺點：?

• 因為含有大量的指針域，占用空間較大；?
• 查找元素需要遍歷鏈表來查找，非常耗時。

JDK提供的鏈表有：java.util.LinkedList

適用場景：?

• 數據量較小，需要頻繁增加，刪除操作的場景；
• 快慢指針：求中間值問題、單向鏈表是否有環問題、有環鏈表入口問題；
• 循環鏈表：約瑟夫問題

2.3?棧(Stack)?

棧是一種特殊的線性表，又稱為棧。是一種基于先進后出（FILO）的數據結構，它只能在表的固定端進行數據結點的插入和刪除操作。棧按照先進后出、后進先出的原則來存儲數據，也就是說，先插入的數據將被壓入棧底，最后插入的數據在棧頂，讀出數據時，從棧頂開始逐個讀出。

棧在匯編語言程序中，經常用于重要數據的現場保護。棧中沒有數據時，稱為空棧 。

我們稱數據進入到棧的動作為壓棧，數據從棧中出去的動作為彈棧。

JDK提供的棧有：java.util.Stack?

應用場景：括號匹配問題；逆波蘭表達式求值問題；實現遞歸功能方面的場景，例如斐波那契數列。

2.4?隊列(Queue)

隊列是一種基于先進先出（FIFO）的數據結構，是一種只能在一端進行插入，在另一端進行刪除操作的特殊線性表，它按照先進先出的原則存儲數據，先進入的數據，在讀取數據時先被讀取出來。

入隊列：進行插入操作的一端稱為隊尾 出隊列：進行刪除操作的一端稱為隊頭

JDK提供的隊列接口有：java.util.Queue

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

2.5?樹(Tree)

樹是典型的非線性結構，它是由n（n>0）個有限結點組成的一個具有層次關系的集合。在樹結構中，有且僅有一個根結點，該結點沒有前驅結點。在樹結構中的其他結點都有且僅有一個前驅結點。

樹具有以下特點：

1. 每個結點有零個或多個子結點；
2. 沒有父結點的結點為根結點；
3. 每一個非根結點只有一個父結點；
4. 除了根節點外，每個子節點可以分為多個不相交的子樹；

在日常的應用中，我們討論和用的更多的是樹的其中一種結構，就是二叉樹、平衡樹、紅黑樹、B樹、B+樹。

應用場景：

1. JDK1.8中?HashMap的底層源碼中用到了數組+鏈表+紅黑樹；
2. 磁盤文件中使用B樹做為數據組織，B樹大大提高了IO的操作效率；
3. mysql數據庫索引結構采用B+樹；

2.5.1?二叉樹：滿二叉樹和完全二叉樹

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

二叉樹有很多擴展的數據結構，包括平衡二叉樹、紅黑樹、B+樹等，這些數據結構在二叉樹的基礎上衍生了很多的功能，在實際應用中廣泛用到，例如mysql的數據庫索引結構用的就是B+樹，還有HashMap的底層源碼中用到了紅黑樹。

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

• 每個結點最多有兩顆子樹，結點的度最大為2。
• 左子樹和右子樹是有順序的，次序不能顛倒。
• 即使某結點只有一個子樹，也要區分左右子樹。

順序結構（數組來存儲，heap里面講）
順序結構存儲就是使用數組來存儲，一般使用數組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現實中使用中只有堆才會使用數組來存儲，。二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹。

鏈式結構
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈，當前我們學習中一般都是二叉鏈，后面課程學到高階數據 結構如紅黑樹等會用到三叉鏈。

鏈式結構接口如下：（包括三種遍歷方式：前序遍歷、中序遍歷、后序遍歷，以及層序遍歷）

2.6?散列表(Hash)

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

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

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

在存儲數據的過程中，如果發生沖突，可以利用鏈表在已有數據的后面插入新數據來解決沖突。這種方法被稱為“鏈地址法”。除了鏈地址法以外，還有幾種解決沖突的方法。其中，應用較為廣泛的是“開放地址法”。

DK提供的哈希表有：java.util.HashMap

散列表應用場景：

• 哈希表的應用場景很多，當然也有很多問題要考慮，比如哈希沖突的問題，如果處理的不好會浪費大量的時間，導致應用崩潰。
• 解決哈希沖突問題：1?可以對數組擴容； 2 優化hash計算方式；

2.7?堆(Heap)

堆是一種特殊的樹形數據結構，一般討論的堆都是二叉堆。堆的特點是根結點的值是所有結點中最小的或者最大的，并且根結點的兩個子樹也是一個堆結構 。

被用于實現“優先隊列”(priority queues)。優先隊列是一種數據結構，可以自由添加數據，但取出數據時要從最小值開始按順序取出。在堆的樹形結構中，各個頂點被稱為“結點”(node)，數據就存儲在這些結點中。堆有下列特點：

• 每個節點最多有兩個子節點
• 排列順序必須從上到下，同一行從左到右
• 堆中某個節點的值總是不大于或不小于其父節點的值；
• 存放數據時，一般會把新數據放在最下面一行靠左的位置。如果最下面一行沒有多余空間時，就再往下另起一行，并把數據添加到這一行的最左端。

堆的性質：

• 堆是一個完全二叉樹
• 堆中某個結點的值總是不大于或不小于其父結點的值；
• 除了樹的最后一層結點不需要是滿的，其它的每一層從左到右都是滿的，如果最后一層結點不是滿的，那么要求左滿右不滿；
• 它通常用數組來實現；

將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、
斐波那契堆等。
一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，
如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹
稱為完全二叉樹。
一棵深度為k且有2^k?1個結點的二叉樹稱為滿二叉樹。也就是說除了葉子節點都有2個子節點，且
所有的葉子節點都在同一層。

堆應用場景：因為堆有序的特點，一般用來做數組中的排序，稱為堆排序。

2.8?圖(Graph)

圖是另一種非線性數據結構。圖的數據結構包含一個有限的集合作為結點集合，以及一個無序對（對應無向圖）或有序對（對應有向圖）的集合作為邊的集合。如果兩個結點之間存在一條邊，那么就表示這兩個結點具有相鄰關系 。

無向圖：

有向圖：

圖的搜索：

• 深度優先搜索：指的是在搜索時，如果遇到一個結點既有子結點，又有兄弟結點，那么先找子結點，然后找兄弟結點。
• 廣度優先搜索：指的是在搜索時，如果遇到一個結點既有子結點，又有兄弟結點，那么先找兄弟結點，然后找子結點。

圖的應用場景：

• 道路暢通工程
• 最短路徑