資料結構想必大家都不會陌生，對于一個成熟的程式員而言，熟悉和掌握資料結構和演算法也是基本功之一，資料結構本身其實不過是資料按照特點關系進行存盤或者組織的集合，特殊的結構在不同的應用場景中往往會帶來不一樣的處理效率，
常用的資料結構可根據資料訪問的特點分為線性結構和非線性結構，線性結構包括常見的鏈表、堆疊、佇列等，非線性結構包括樹、圖等，資料結構種類繁多，本文將通過圖解的方式對常用的資料結構進行理論上的介紹和講解，以方便大家掌握常用資料結構的基本知識，
一、陣列
陣列可以說是最基本最常見的資料結構，陣列一般用來存盤相同型別的資料，可通過陣列名和下標進行資料的訪問和更新，陣列中元素的存盤是按照先后順序進行的，同時在記憶體中也是按照這個順序進行連續存放，陣列相鄰元素之間的記憶體地址的間隔一般就是陣列資料型別的大小，
二、鏈表
鏈表相較于陣列，除了資料域，還增加了指標域用于構建鏈式的存盤資料，鏈表中每一個節點都包含此節點的資料和指向下一節點地址的指標，由于是通過指標進行下一個資料元素的查找和訪問，使得鏈表的自由度更高，
這表現在對節點進行增加和洗掉時，只需要對上一節點的指標地址進行修改，而無需變動其它的節點，不過事物皆有兩極，指標帶來高自由度的同時，自然會犧牲資料查找的效率和多余空間的使用，
一般常見的是有頭有尾的單鏈表，對指標域進行反向鏈接，還可以形成雙向鏈表或者回圈鏈表，
鏈表和陣列對比
鏈表和陣列在實際的使用程序中需要根據自身的優劣勢進行選擇，鏈表和陣列的異同點也是面試中高頻的考察點之一，這里對單鏈表和陣列的區別進行了對比和總結，
三、跳表
從上面的對比中可以看出，鏈表雖然通過增加指標域提升了自由度，但是卻導致資料的查詢效率惡化，特別是當鏈表長度很長的時候，對資料的查詢還得從頭依次查詢，這樣的效率會更低，跳表的產生就是為了解決鏈表過長的問題，通過增加鏈表的多級索引來加快原始鏈表的查詢效率，這樣的方式可以讓查詢的時間復雜度從O(n)提升至O(logn)，
跳表通過增加的多級索引能夠實作高效的動態插入和洗掉，其效率和紅黑樹和平衡二叉樹不相上下，目前redis和levelDB都有用到跳表，
從上圖可以看出，索引級的指標域除了指向下一個索引位置的指標，還有一個down指標指向低一級的鏈表位置，這樣才能實作跳躍查詢的目的，
四、堆疊
堆疊是一種比較簡單的資料結構，常用一句話描述其特性，后進先出，堆疊本身是一種線性結構，但是在這個結構中只有一個口子允許資料的進出，這種模式可以參考腔腸動物...即進食和排泄都用一個口...
堆疊的常用操作包括入堆疊push和出堆疊pop，對應于資料的壓入和壓出，還有訪問堆疊頂資料、判斷堆疊是否為空和判斷堆疊的大小等，由于堆疊后進先出的特性，常可以作為資料操作的臨時容器，對資料的順序進行調控，與其它資料結構相結合可獲得許多靈活的處理，
五、佇列
佇列是堆疊的兄弟結構，與堆疊的后進先出相對應，佇列是一種先進先出的資料結構，顧名思義，佇列的資料存盤是如同排隊一般，先存入的資料先被壓出，常與堆疊一同配合，可發揮最大的實力，
六、樹
樹作為一種樹狀的資料結構，其資料節點之間的關系也如大樹一樣，將有限個節點根據不同層次關系進行排列，從而形成資料與資料之間的父子關系，常見的數的表示形式更接近“倒掛的樹”，因為它將根朝上，葉朝下，
樹的資料存盤在結點中，每個結點有零個或者多個子結點，沒有父結點的結點在最頂端，成為根節點；沒有非根結點有且只有一個父節點；每個非根節點又可以分為多個不相交的子樹，
這意味著樹是具備層次關系的，父子關系清晰，家庭血緣關系明朗；這也是樹與圖之間最主要的區別，
別看樹好像很高級，其實可看作是鏈表的高配版，樹的實作就是對鏈表的指標域進行了擴充，增加了多個地址指向子結點，同時將“鏈表”豎起來，從而凸顯了結點之間的層次關系，更便于分析和理解，
樹可以衍生出許多的結構，若將指標域設定為雙指標，那么即可形成最常見的二叉樹，即每個結點最多有兩個子樹的樹結構，二叉樹根據結點的排列和數量還可進一度劃分為完全二叉樹、滿二叉樹、平衡二叉樹、紅黑樹等，
完全二叉樹：除了最后一層結點，其它層的結點數都達到了最大值；同時最后一層的結點都是按照從左到右依次排布，
滿二叉樹：除了最后一層，其它層的結點都有兩個子結點，
平衡二叉樹
平衡二叉樹又被稱為AVL樹，它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，
二叉排序樹：是一棵空樹，或者：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分別為二叉排序樹，
樹的高度：結點層次的最大值
平衡因子：左子樹高度 - 右子樹高度
二叉排序樹意味著二叉樹中的資料是排好序的，順序為左結點<根節點<右結點，這表明二叉排序樹的中序遍歷結果是有序的，
平衡二叉樹的產生是為了解決二叉排序樹在插入時發生線性排列的現象，由于二叉排序樹本身為有序，當插入一個有序程度十分高的序列時，生成的二叉排序樹會持續在某個方向的字數上插入資料，導致最終的二叉排序樹會退化為鏈表，從而使得二叉樹的查詢和插入效率惡化，
平衡二叉樹的出現能夠解決上述問題，但是在構造平衡二叉樹時，卻需要采用不同的調整方式，使得二叉樹在插入資料后保持平衡，主要的四種調整方式有LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋），這里先給大家介紹下簡單的單旋轉操作，左旋和右旋，LR和RL本質上只是LL和RR的組合，
在插入一個結點后應該沿搜索路徑將路徑上的結點平衡因子進行修改，當平衡因子大于1時，就需要進行平衡化處理，從發生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點，如果這三個結點在一條直線上，則采用單旋轉進行平衡化，如果這三個結點位于一條折線上，則采用雙旋轉進行平衡化，
左旋：S為當前需要左旋的結點，E為當前結點的父節點，
左旋的操作可以用一句話簡單表示：將當前結點S的左孩子旋轉為當前結點父結點E的右孩子，同時將父結點E旋轉為當前結點S的左孩子，可用影片表示：
右旋：S為當前需要左旋的結點，E為當前結點的父節點，右單旋是左單旋的鏡像旋轉，
左旋的操作同樣可以用一句話簡單表示：將當前結點S的左孩子E的右孩子旋轉為當前結點S的左孩子，同時將當前結點S旋轉為左孩子E的右孩子，可用影片表示：
紅黑樹
平衡二叉樹（AVL）為了追求高度平衡，需要通過平衡處理使得左右子樹的高度差必須小于等于1，高度平衡帶來的好處是能夠提供更高的搜索效率，其最壞的查找時間復雜度都是O(logN)，但是由于需要維持這份高度平衡，所付出的代價就是當對樹種結點進行插入和洗掉時，需要經過多次旋轉實作復衡，這導致AVL的插入和洗掉效率并不高，
為了解決這樣的問題，能不能找一種結構能夠兼顧搜索和插入洗掉的效率呢？這時候紅黑樹便申請出戰了，
紅黑樹具有五個特性：
- 每個結點要么是紅的要么是黑的，
- 根結點是黑的，
- 每個葉結點（葉結點即指樹尾端NIL指標或NULL結點）都是黑的，
- 如果一個結點是紅的，那么它的兩個兒子都是黑的，
- 對于任意結點而言，其到葉結點樹尾端NIL指標的每條路徑都包含相同數目的黑結點，
紅黑樹通過將結點進行紅黑著色，使得原本高度平衡的樹結構被稍微打亂，平衡程度降低，紅黑樹不追求完全平衡，只要求達到部分平衡，這是一種折中的方案，大大提高了結點洗掉和插入的效率，C++中的STL就常用到紅黑樹作為底層的資料結構，
紅黑樹VS平衡二叉樹
除了上面所提及的樹結構，還有許多廣泛應用在資料庫、磁盤存盤等場景下的樹結構，比如B樹、B+樹等，這里就先不介紹了誒，下次在講述相關存盤原理的時候將會著重介紹，（其實是因為懶）
七、堆
了解完二叉樹，再來理解堆就不是什么難事了，堆通常是一個可以被看做一棵樹的陣列物件，堆的具體實作一般不通過指標域，而是通過構建一個一維陣列與二叉樹的父子結點進行對應，因此堆總是一顆完全二叉樹，
對于任意一個父節點的序號n來說（這里n從0算），它的子節點的序號一定是2n+1，2n+2，因此可以直接用陣列來表示一個堆，
不僅如此，堆還有一個性質：堆中某個節點的值總是不大于或不小于其父節點的值，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
堆常用來實作優先佇列，在面試中經常考的問題都是與排序有關，比如堆排序、topK問題等，由于堆的根節點是序列中最大或者最小值，因而可以在建堆以及重建堆的程序中，篩選出資料序列中的極值，從而達到排序或者挑選topK值的目的，
八、散串列
散串列也叫哈希表，是一種通過鍵值對直接訪問資料的機構，在初中，我們就學過一種能夠將一個x值通過一個函式獲得對應的一個y值的操作，叫做映射，散串列的實作原理正是映射的原理，通過設定的一個關鍵字和一個映射函式，就可以直接獲得訪問資料的地址，實作O(1)的資料訪問效率，在映射的程序中，事先設定的函式就是一個映射表，也可以稱作散列函式或者哈希函式，
散串列的實作最關鍵的就是散列函式的定義和選擇，一般常用的有以下幾種散列函式：
直接尋址法：取關鍵字或關鍵字的某個線性函式值為散列地址，
數字分析法：通過對資料的分析，發現資料中沖突較少的部分，并構造散列地址，例如同學們的學號，通常同一屆學生的學號，其中前面的部分差別不太大，所以用后面的部分來構造散列地址，
平方取中****法：當無法確定關鍵字里哪幾位的分布相對比較均勻時，可以先求出關鍵字的平方值，然后按需要取平方值的中間幾位作為散列地址，這是因為：計算平方之后的中間幾位和關鍵字中的每一位都相關，所以不同的關鍵字會以較高的概率產生不同的散列地址，
取亂數法：使用一個隨機函式，取關鍵字的隨機值作為散列地址，這種方式通常用于關鍵字長度不同的場合，
除留取余法：取關鍵字被某個不大于散串列的表長 n 的數 m 除后所得的余數 p 為散列地址，這種方式也可以在用過其他方法后再使用，該函式對 m 的選擇很重要，一般取素數或者直接用 n，
確定好散列函式之后，通過某個key值的確會得到一個唯一的value地址，但是卻會出現一些特殊情況，即通過不同的key值可能會訪問到同一個地址，這個現象稱之為沖突，
沖突在發生之后，當在對不同的key值進行操作時會使得造成相同地址的資料發生覆寫或者丟失，是非常危險的，所以在設計散串列往往還需要采用沖突解決的辦法，
常用的沖突處理方式有很多，常用的包括以下幾種：
開放地址法（也叫開放尋址法）：實際上就是當需要存盤值時，對Key哈希之后，發現這個地址已經有值了，這時該怎么辦？不能放在這個地址，不然之前的映射會被覆寫，這時對計算出來的地址進行一個探測再哈希，比如往后移動一個地址，如果沒人占用，就用這個地址，如果超過最大長度，則可以對總長度取余，這里移動的地址是產生沖突時的增列序量，
再哈希法：在產生沖突之后，使用關鍵字的其他部分繼續計算地址，如果還是有沖突，則繼續使用其他部分再計算地址，這種方式的缺點是時間增加了，
鏈地址法：鏈地址法其實就是對Key通過哈希之后落在同一個地址上的值，做一個鏈表，其實在很多高級語言的實作當中，也是使用這種方式處理沖突的，
公共溢位區：這種方式是建立一個公共溢位區，當地址存在沖突時，把新的地址放在公共溢位區里，
目前比較常用的沖突解決方法是鏈地址法，一般可以通過陣列和鏈表的結合達到沖突資料快取的目的，
左側陣列的每個成員包括一個指標，指向一個鏈表的頭，每發生一個沖突的資料，就將該資料作為鏈表的節點鏈接到鏈表尾部，這樣一來，就可以保證沖突的資料能夠區分并順利訪問，
考慮到鏈表過長造成的問題，還可以使用紅黑樹替換鏈表進行沖突資料的處理操作，來提高散串列的查詢穩定性，
九、圖
圖相較于上文的幾個結構可能接觸的不多，但是在實際的應用場景中卻經常出現，比方說交通中的線路圖，常見的思維導圖都可以看作是圖的具體表現形式，
圖結構一般包括頂點和邊，頂點通常用圓圈來表示，邊就是這些圓圈之間的連線，邊還可以根據頂點之間的關系設定不同的權重，默認權重相同皆為1，此外根據邊的方向性，還可將圖分為有向圖和無向圖，
圖結構用抽象的圖線來表示十分簡單，頂點和邊之間的關系非常清晰明了，但是在具體的代碼實作中，為了將各個頂點和邊的關系存盤下來，卻不是一件易事，
鄰接矩陣
目前常用的圖存盤方式為鄰接矩陣，通過所有頂點的二維矩陣來存盤兩個頂點之間是否相連，或者存盤兩頂點間的邊權重，
無向圖的鄰接矩陣是一個對稱矩陣，是因為邊不具有方向性，若能從此頂點能夠到達彼頂點，那么彼頂點自然也能夠達到此頂點，此外，由于頂點本身與本身相連沒有意義，所以在鄰接矩陣中對角線上皆為0，
有向圖由于邊具有方向性，因此彼此頂點之間并不能相互達到，所以其鄰接矩陣的對稱性不再，
用鄰接矩陣可以直接從二維關系中獲得任意兩個頂點的關系，可直接判斷是否相連，但是在對矩陣進行存盤時，卻需要完整的一個二維陣列，若圖中頂點數過多，會導致二維陣列的大小劇增，從而占用大量的記憶體空間，
而根據實際情況可以分析得，圖中的頂點并不是任意兩個頂點間都會相連，不是都需要對其邊上權重進行存盤，那么存盤的鄰接矩陣實際上會存在大量的0，雖然可以通過稀疏表示等方式對稀疏性高的矩陣進行關鍵資訊的存盤，但是卻增加了圖存盤的復雜性，
因此，為了解決上述問題，一種可以只存盤相連頂點關系的鄰接表應運而生，
鄰接表
在鄰接表中，圖的每一個頂點都是一個鏈表的頭節點，其后連接著該頂點能夠直接達到的相鄰頂點，相較于無向圖，有向圖的情況更為復雜，因此這里采用有向圖進行實體分析，
在鄰接表中，每一個頂點都對應著一條鏈表，鏈表中存盤的是頂點能夠達到的相鄰頂點，存盤的順序可以按照頂點的編號順序進行，比如上圖中對于頂點B來說，其通過有向邊可以到達頂點A和頂點E，那么其對應的鄰接表中的順序即B->A->E，其它頂點亦如此，
通過鄰接表可以獲得從某個頂點出發能夠到達的頂點，從而省去了對不相連頂點的存盤空間，然而，這還不夠，對于有向圖而言，圖中有效資訊除了從頂點“指出去”的資訊，還包括從別的頂點“指進來”的資訊，這里的“指出去”和“指進來”可以用出度和入度來表示，
入度：有向圖的某個頂點作為終點的次數和，
出度：有向圖的某個頂點作為起點的次數和，
由此看出，在對有向圖進行表示時，鄰接表只能求出圖的出度，而無法求出入度，這個問題很好解決，那就是增加一個表用來存盤能夠到達某個頂點的相鄰頂點，這個表稱作逆鄰接表，
逆鄰接表
逆鄰接表與鄰接表結構類似，只不過圖的頂點鏈接著能夠到達該頂點的相鄰頂點，也就是說，鄰接表時順著圖中的箭頭尋找相鄰頂點，而逆鄰接表時逆著圖中的箭頭尋找相鄰頂點，
鄰接表和逆鄰接表的共同使用下，就能夠把一個完整的有向圖結構進行表示，可以發現，鄰接表和逆鄰接表實際上有一部分資料時重合的，因此可以將兩個表合二為一，從而得到了所謂的十字鏈表，
十字鏈表
十字鏈表似乎很簡單，只需要通過相同的頂點分別鏈向以該頂點為終點和起點的相鄰頂點即可，
但這并不是最優的表示方式，雖然這樣的方式共用了中間的頂點存盤空間，但是鄰接表和逆鄰接表的鏈表節點中重復出現的頂點并沒有得到重復利用，反而是進行了再次存盤，因此，上圖的表示方式還可以進行進一步優化，
十字鏈表優化后，可通過擴展的頂點結構和邊結構來進行正逆鄰接表的存盤：（下面的弧頭可看作是邊的箭頭那端，弧尾可看作是邊的圓點那端）
data：用于存盤該頂點中的資料；
firstin指標：用于連接以當前頂點為弧頭的其他頂點構成的鏈表，即從別的頂點指進來的頂點；
firstout指標：用于連接以當前頂點為弧尾的其他頂點構成的鏈表，即從該頂點指出去的頂點；
邊結構通過存盤兩個頂點來確定一條邊，同時通過分別代表這兩個頂點的指標來與相鄰頂點進行鏈接：
tailvex：用于存盤作為弧尾的頂點的編號；
headvex：用于存盤作為弧頭的頂點的編號；
headlink ****指標：用于鏈接下一個存盤作為弧頭的頂點的節點；
taillink ****指標：用于鏈接下一個存盤作為弧尾的頂點的節點；
以上圖為例子，對于頂點A而言，其作為起點能夠到達頂點E，因此在鄰接表中頂點A要通過邊AE（即邊04）指向頂點E，頂點A的firstout指標需要指向邊04的tailvex，同時，從B出發能夠到達A，所以在逆鄰接表中頂點A要通過邊AB（即邊10）指向B，頂點A的firstin指標需要指向邊10的弧頭，即headlink指標，依次類推，
十字鏈表采用了一種看起來比較繁亂的方式對邊的方向性進行了表示，能夠在盡可能降低存盤空間的情況下增加指標保留頂點之間的方向性，具體的操作可能一時間不好弄懂，建議多看幾次上圖，弄清指標指向的意義，明白正向和逆向鄰接表的表示，
總結
資料結構博大精深，沒有高等數學的諱莫如深，也沒有量子力學的玄乎其神，但是其在計算機科學的各個領域都具有強大的力量，本文試圖采用圖解的方式對九種資料結構進行理論上的介紹，但是其實這都是不夠的，
即便是簡單的陣列、堆疊、佇列等結構，在實際使用以及底層實作上都會有許多優化設計以及使用技巧，這意味著還需要真正把它們靈活的用起來，才能夠算是真正意義上的熟悉和精通，但是本文可以作為常見資料結構的一個總結，當你對某些結構有些淡忘的時候，不妨重新回來看看，
寫在最后
歡迎大家關注我的公眾號【風平浪靜如碼】，海量Java相關文章，學習資料都會在里面更新，整理的資料也會放在里面，
覺得寫的還不錯的就點個贊，加個關注唄！點關注，不迷路，持續更新！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243112.html
標籤：Java