前幾天和敖丙交流，他說我們寫作的人都是在不停地燃燒自己，所以需要不停地補充燃料，對于他的觀點，我不能再茍同了——所以我開始狂補計算機方面的基礎知識，這其中就包括我相對薄弱的資料結構，
請肆無忌憚地點贊吧，微信搜索【沉默王二】關注這個在十三朝古都洛陽茍且偷生的程式員，
本文 GitHub github.com/itwanger 已收錄，里面還有我精心為你準備的一線大廠面試題，
百度百科對資料結構的定義是：相互之間存在一種或多種特定關系的資料元素的集合，定義很抽象，需要大聲地朗讀幾遍，才有點感覺，怎么讓這種感覺來得更強烈，更親切一些呢？我來列舉一下常見的 8 種資料結構，陣列、鏈表、堆疊、佇列、樹、堆、圖、哈希表，
這 8 種資料結構有什么區別呢？
①、陣列
優點：
- 按照索引查詢元素的速度很快；
- 按照索引遍歷陣列也很方便，
缺點：
- 陣列的大小在創建后就確定了，無法擴容；
- 陣列只能存盤一種型別的資料；
- 添加、洗掉元素的操作很耗時間，因為要移動其他元素，
②、鏈表
《演算法（第 4 版）》一書中是這樣定義鏈表的：
鏈表是一種遞回的資料結構，它或者為空（null），或者是指向一個結點（node）的參考，該節點還有一個元素和一個指向另一條鏈表的參考，
Java 的 LinkedList 類可以很形象地通過代碼的形式來表示一個鏈表的結構：
public class LinkedList<E> {
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
這是一種雙向鏈表，當前元素 item 既有 prev 又有 next，不過 first 的 prev 為 null，last 的 next 為 null，如果是單向鏈表的話，就只有 next，沒有 prev，
單向鏈表的缺點是只能從頭到尾依次遍歷，而雙向鏈表可進可退，既能找到下一個，也能找到上一個——每個節點上都需要多分配一個存盤空間，
鏈表中的資料按照“鏈式”的結構存盤，因此可以達到記憶體上非連續的效果，陣列必須是一塊連續的記憶體，
由于不必按照順序的方式存盤，鏈表在插入、洗掉的時候可以達到 O(1) 的時間復雜度（只需要重新指向參考即可，不需要像陣列那樣移動其他元素），除此之外，鏈表還克服了陣列必須預先知道資料大小的缺點，從而可以實作靈活的記憶體動態管理，
優點：
- 不需要初始化容量；
- 可以添加任意元素；
- 插入和洗掉的時候只需要更新參考，
缺點：
- 含有大量的參考，占用的記憶體空間大；
- 查找元素需要遍歷整個鏈表，耗時，
③、堆疊
堆疊就好像水桶一樣，底部是密封的，頂部是開口，水可以進可以出，用過水桶的小伙伴應該明白這樣一個道理：先進去的水在桶的底部，后進去的水在桶的頂部；后進去的水先被倒出來，先進去的水后被倒出來，
同理，堆疊按照“后進先出”、“先進后出”的原則來存盤資料，先插入的資料被壓入堆疊底，后插入的資料在堆疊頂，讀出資料的時候，從堆疊頂開始依次讀出，
④、佇列
佇列就好像一段水管一樣，兩端都是開口的，水從一端進去，然后從另外一端出來，先進去的水先出來，后進去的水后出來，
和水管有些不同的是，佇列會對兩端進行定義，一端叫隊頭，另外一端就叫隊尾，隊頭只允許洗掉操作（出隊），隊尾只允許插入操作（入隊），
注意，堆疊是先進后出，佇列是先進先出——兩者雖然都是線性表，但原則是不同的，結構不一樣嘛，
⑤、樹
樹是一種典型的非線性結構，它是由 n（n>0）個有限節點組成的一個具有層次關系的集合，
之所以叫“樹”，是因為這種資料結構看起來就像是一個倒掛的樹，只不過根在上，葉在下，樹形資料結構有以下這些特點：
- 每個節點都只有有限個子節點或無子節點；
- 沒有父節點的節點稱為根節點；
- 每一個非根節點有且只有一個父節點；
- 除了根節點外，每個子節點可以分為多個不相交的子樹，
下圖展示了樹的一些術語：
根節點是第 0 層，它的子節點是第 1 層，子節點的子節點為第 2 層，以此類推，
- 深度：對于任意節點 n，n 的深度為從根到 n 的唯一路徑長，根的深度為 0，
- 高度：對于任意節點 n，n 的高度為從 n 到一片樹葉的最長路徑長，所有樹葉的高度為 0，
樹的種類有很多種，常見的有：
- 無序樹：樹中任意節點的子節點之間沒有順序關系，那怎么來理解無序樹呢，到底長什么樣子？
假如有三個節點，一個是父節點，兩個是同級的子節點，那么就有三種情況：
假如有三個節點，一個是父節點，兩個是不同級的子節點，那么就有六種情況：
三個節點組成的無序樹，合起來就是九種情況，
- 二叉樹：每個節點最多含有兩個子樹，二叉樹按照不同的表現形式又可以分為多種，
完全二叉樹：對于一顆二叉樹，假設其深度為 d（d > 1），除了第 d 層，其它各層的節點數目均已達最大值，且第 d 層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹，
拿上圖來說，d 為 3，除了第 3 層，第 1 層、第 2 層 都達到了最大值（2 個子節點），并且第 3 層的所有節點從左向右聯系地緊密排列（H、I、J、K、L），符合完全二叉樹的要求，
滿二叉樹：一顆每一層的節點數都達到了最大值的二叉樹，有兩種表現形式，第一種，像下圖這樣（每一層都是滿的），滿足每一層的節點數都達到了最大值 2，
第二種，像下圖這樣（每一層雖然不滿），但每一層的節點數仍然達到了最大值 2，
二叉查找樹：英文名叫 Binary Search Tree，即 BST，需要滿足以下條件：
- 任意節點的左子樹不空，左子樹上所有節點的值均小于它的根節點的值；
- 任意節點的右子樹不空，右子樹上所有節點的值均大于它的根節點的值；
- 任意節點的左、右子樹也分別為二叉查找樹，
基于二叉查找樹的特點，它相比較于其他資料結構的優勢就在于查找、插入的時間復雜度較低，為 O(logn)，假如我們要從上圖中查找 5 個元素，先從根節點 7 開始找，5 必定在 7 的左側，找到 4，那 5 必定在 4 的右側，找到 6，那 5 必定在 6 的左側，找到了，
理想情況下，通過 BST 查找節點，所需要檢查的節點數可以減半，
平衡二叉樹：當且僅當任何節點的兩棵子樹的高度差不大于 1 的二叉樹，由前蘇聯的數學家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉樹，根據科學家的英文名也稱為 AVL 樹，
平衡二叉樹本質上也是一顆二叉查找樹，不過為了限制左右子樹的高度差，避免出現傾斜樹等偏向于線性結構演化的情況，所以對二叉搜索樹中每個節點的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個節點的平衡因子絕對值不大于 1，
平衡二叉樹的難點在于，當洗掉或者增加節點的情況下，如何通過左旋或者右旋的方式來保持左右平衡，
Java 中最常見的平衡二叉樹就是紅黑樹，節點是紅色或者黑色，通過顏色的約束來維持著二叉樹的平衡：
1）每個節點都只能是紅色或者黑色
2）根節點是黑色
3）每個葉節點（NIL 節點，空節點）是黑色的，
4）如果一個節點是紅色的，則它兩個子節點都是黑色的，也就是說在一條路徑上不能出現相鄰的兩個紅色節點，
5）從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點，
- B 樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持資料有序，擁有多于兩個的子樹，資料庫的索引技術里就用到了 B 樹，
⑥、堆
堆可以被看做是一棵樹的陣列物件，具有以下特點：
- 堆中某個節點的值總是不大于或不小于其父節點的值；
- 堆總是一棵完全二叉樹，
將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
⑦、圖
圖是一種復雜的非線性結構，由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G 表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合，
上圖共有 V0，V1，V2，V3 這 4 個頂點，4 個頂點之間共有 5 條邊，
在線性結構中，資料元素之間滿足唯一的線性關系，每個資料元素（除第一個和最后一個外）均有唯一的“前驅”和“后繼”；
在樹形結構中，資料元素之間有著明顯的層次關系，并且每個資料元素只與上一層中的一個元素（父節點）及下一層的多個元素（子節點）相關；
而在圖形結構中，節點之間的關系是任意的，圖中任意兩個資料元素之間都有可能相關，
⑧、哈希表
哈希表（Hash Table），也叫散串列，是一種可以通過關鍵碼值（key-value）直接訪問的資料結構，它最大的特點就是可以快速實作查找、插入和洗掉，
陣列的最大特點就是查找容易，插入和洗掉困難；而鏈表正好相反，查找困難，而插入和洗掉容易，哈希表很完美地結合了兩者的優點， Java 的 HashMap 在此基礎上還加入了樹的優點，
哈希函式在哈希表中起著?常關鍵的作?，它可以把任意長度的輸入變換成固定長度的輸出，該輸出就是哈希值，哈希函式使得一個資料序列的訪問程序變得更加迅速有效，通過哈希函式，資料元素能夠被很快的進行定位，
若關鍵字為 k，則其值存放在 hash(k) 的存盤位置上，由此，不需要遍歷就可以直接取得 k 對應的值，
對于任意兩個不同的資料塊，其哈希值相同的可能性極小，也就是說，對于一個給定的資料塊，找到和它哈希值相同的資料塊極為困難，再者，對于一個資料塊，哪怕只改動它的一個位元位，其哈希值的改動也會非常的大——這正是 Hash 存在的價值！
盡管可能性極小，但仍然會發生，如果哈希沖突了，Java 的 HashMap 會在陣列的同一個位置上增加鏈表，如果鏈表的長度大于 8，將會轉化成紅黑樹進行處理——這就是所謂的拉鏈法（陣列+鏈表），
說句實在話，照這個進度惡補下去，我感覺要禿的節奏，不過，如果能夠變得更強，值了——對，值了，
我是沉默王二，一枚沉默但有趣的程式員，關注即可提升學習效率，喜歡這篇文章的小伙伴，請不要忘記四聯啊，點贊、收藏、轉發、留言，你最美你最帥！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/104942.html
標籤：Java
上一篇：總結類初始化時，代碼執行順序
下一篇：虛擬機系列 | JVM類加載機制