java中常見的數(shù)據(jù)結(jié)構(gòu)有哪些

①、數(shù)組

優(yōu)點(diǎn)：

• 按照索引查詢元素的速度很快；

• 按照索引遍歷數(shù)組也很方便。

缺點(diǎn)：

• 數(shù)組的大小在創(chuàng)建后就確定了，無法擴(kuò)容；

• 數(shù)組只能存儲一種類型的數(shù)據(jù)；

• 添加、刪除元素的操作很耗時(shí)間，因?yàn)橐苿悠渌亍?/p>

②、鏈表

《算法（第 4 版）》一書中是這樣定義鏈表的：

鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者為空（null），或者是指向一個(gè)結(jié)點(diǎn)（node）的引用，該節(jié)點(diǎn)還有一個(gè)元素和一個(gè)指向另一條鏈表的引用。

Java 的 LinkedList 類可以很形象地通過代碼的形式來表示一個(gè)鏈表的結(jié)構(gòu)：

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;
        }
    }
}

這是一種雙向鏈表，當(dāng)前元素 item 既有 prev 又有 next，不過 first 的 prev 為 null，last 的 next 為 null。如果是單向鏈表的話，就只有 next，沒有 prev。

 

單向鏈表的缺點(diǎn)是只能從頭到尾依次遍歷，而雙向鏈表可進(jìn)可退，既能找到下一個(gè)，也能找到上一個(gè)——每個(gè)節(jié)點(diǎn)上都需要多分配一個(gè)存儲空間。

鏈表中的數(shù)據(jù)按照“鏈?zhǔn)健钡慕Y(jié)構(gòu)存儲，因此可以達(dá)到內(nèi)存上非連續(xù)的效果，數(shù)組必須是一塊連續(xù)的內(nèi)存。

 

由于不必按照順序的方式存儲，鏈表在插入、刪除的時(shí)候可以達(dá)到 O(1) 的時(shí)間復(fù)雜度（只需要重新指向引用即可，不需要像數(shù)組那樣移動其他元素）。除此之外，鏈表還克服了數(shù)組必須預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，從而可以實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理。

優(yōu)點(diǎn)：

• 不需要初始化容量；

• 可以添加任意元素；

• 插入和刪除的時(shí)候只需要更新引用。

缺點(diǎn)：

• 含有大量的引用，占用的內(nèi)存空間大；

• 查找元素需要遍歷整個(gè)鏈表，耗時(shí)。

③、棧

棧就好像水桶一樣，底部是密封的，頂部是開口，水可以進(jìn)可以出。用過水桶的小伙伴應(yīng)該明白這樣一個(gè)道理：先進(jìn)去的水在桶的底部，后進(jìn)去的水在桶的頂部；后進(jìn)去的水先被倒出來，先進(jìn)去的水后被倒出來。

同理，棧按照“后進(jìn)先出”、“先進(jìn)后出”的原則來存儲數(shù)據(jù)，先插入的數(shù)據(jù)被壓入棧底，后插入的數(shù)據(jù)在棧頂，讀出數(shù)據(jù)的時(shí)候，從棧頂開始依次讀出。

 

④、隊(duì)列

隊(duì)列就好像一段水管一樣，兩端都是開口的，水從一端進(jìn)去，然后從另外一端出來。先進(jìn)去的水先出來，后進(jìn)去的水后出來。

和水管有些不同的是，隊(duì)列會對兩端進(jìn)行定義，一端叫隊(duì)頭，另外一端就叫隊(duì)尾。隊(duì)頭只允許刪除操作（出隊(duì)），隊(duì)尾只允許插入操作（入隊(duì)）。

 

注意，棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出——兩者雖然都是線性表，但原則是不同的，結(jié)構(gòu)不一樣嘛。

⑤、樹

樹是一種典型的非線性結(jié)構(gòu)，它是由 n（n>0）個(gè)有限節(jié)點(diǎn)組成的一個(gè)具有層次關(guān)系的集合。

 

之所以叫“樹”，是因?yàn)檫@種數(shù)據(jù)結(jié)構(gòu)看起來就像是一個(gè)倒掛的樹，只不過根在上，葉在下。樹形數(shù)據(jù)結(jié)構(gòu)有以下這些特點(diǎn)：

• 每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無子節(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è)不相交的子樹。

下圖展示了樹的一些術(shù)語：

 

根節(jié)點(diǎn)是第 0 層，它的子節(jié)點(diǎn)是第 1 層，子節(jié)點(diǎn)的子節(jié)點(diǎn)為第 2 層，以此類推。

• 深度：對于任意節(jié)點(diǎn) n，n 的深度為從根到 n 的唯一路徑長，根的深度為 0。

• 高度：對于任意節(jié)點(diǎn) n，n 的高度為從 n 到一片樹葉的最長路徑長，所有樹葉的高度為 0。

樹的種類有很多種，常見的有：

• 無序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系。那怎么來理解無序樹呢，到底長什么樣子？

假如有三個(gè)節(jié)點(diǎn)，一個(gè)是父節(jié)點(diǎn)，兩個(gè)是同級的子節(jié)點(diǎn)，那么就有三種情況：

 

假如有三個(gè)節(jié)點(diǎn)，一個(gè)是父節(jié)點(diǎn)，兩個(gè)是不同級的子節(jié)點(diǎn)，那么就有六種情況：

 

三個(gè)節(jié)點(diǎn)組成的無序樹，合起來就是九種情況。

• 二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹。二叉樹按照不同的表現(xiàn)形式又可以分為多種。

完全二叉樹：對于一顆二叉樹，假設(shè)其深度為 d（d > 1）。除了第 d 層，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第 d 層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹。

 

拿上圖來說，d 為 3，除了第 3 層，第 1 層、第 2 層 都達(dá)到了最大值（2 個(gè)子節(jié)點(diǎn)），并且第 3 層的所有節(jié)點(diǎn)從左向右聯(lián)系地緊密排列（H、I、J、K、L），符合完全二叉樹的要求。

滿二叉樹：一顆每一層的節(jié)點(diǎn)數(shù)都達(dá)到了最大值的二叉樹。有兩種表現(xiàn)形式，第一種，像下圖這樣（每一層都是滿的），滿足每一層的節(jié)點(diǎn)數(shù)都達(dá)到了最大值 2。

 

第二種，像下圖這樣（每一層雖然不滿），但每一層的節(jié)點(diǎn)數(shù)仍然達(dá)到了最大值 2。

 

二叉查找樹：英文名叫 Binary Search Tree，即 BST，需要滿足以下條件：

• 任意節(jié)點(diǎn)的左子樹不空，左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；

• 任意節(jié)點(diǎn)的右子樹不空，右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；

• 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

 

基于二叉查找樹的特點(diǎn)，它相比較于其他數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢就在于查找、插入的時(shí)間復(fù)雜度較低，為 O(logn)。假如我們要從上圖中查找 5 個(gè)元素，先從根節(jié)點(diǎn) 7 開始找，5 必定在 7 的左側(cè)，找到 4，那 5 必定在 4 的右側(cè)，找到 6，那 5 必定在 6 的左側(cè)，找到了。

理想情況下，通過 BST 查找節(jié)點(diǎn)，所需要檢查的節(jié)點(diǎn)數(shù)可以減半。

平衡二叉樹：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹的高度差不大于 1 的二叉樹。由前蘇聯(lián)的數(shù)學(xué)家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉樹，根據(jù)科學(xué)家的英文名也稱為 AVL 樹。

平衡二叉樹本質(zhì)上也是一顆二叉查找樹，不過為了限制左右子樹的高度差，避免出現(xiàn)傾斜樹等偏向于線性結(jié)構(gòu)演化的情況，所以對二叉搜索樹中每個(gè)節(jié)點(diǎn)的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個(gè)節(jié)點(diǎn)的平衡因子絕對值不大于 1。

平衡二叉樹的難點(diǎn)在于，當(dāng)刪除或者增加節(jié)點(diǎn)的情況下，如何通過左旋或者右旋的方式來保持左右平衡。

Java 中最常見的平衡二叉樹就是紅黑樹，節(jié)點(diǎn)是紅色或者黑色，通過顏色的約束來維持著二叉樹的平衡：

1）每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色

2）根節(jié)點(diǎn)是黑色

3）每個(gè)葉節(jié)點(diǎn)（NIL 節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。

4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它兩個(gè)子節(jié)點(diǎn)都是黑色的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色節(jié)點(diǎn)。

5）從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

 

• B 樹：一種對讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多于兩個(gè)的子樹。數(shù)據(jù)庫的索引技術(shù)里就用到了 B 樹。

 

⑥、堆

堆可以被看做是一棵樹的數(shù)組對象，具有以下特點(diǎn)：

• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

• 堆總是一棵完全二叉樹。

將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

 

⑦、圖

圖是一種復(fù)雜的非線性結(jié)構(gòu)，由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G（V，E），其中，G 表示一個(gè)圖，V 是圖 G 中頂點(diǎn)的集合，E 是圖 G 中邊的集合。

 

上圖共有 V0，V1，V2，V3 這 4 個(gè)頂點(diǎn)，4 個(gè)頂點(diǎn)之間共有 5 條邊。

在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間滿足唯一的線性關(guān)系，每個(gè)數(shù)據(jù)元素（除第一個(gè)和最后一個(gè)外）均有唯一的“前驅(qū)”和“后繼”；

在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每個(gè)數(shù)據(jù)元素只與上一層中的一個(gè)元素（父節(jié)點(diǎn)）及下一層的多個(gè)元素（子節(jié)點(diǎn)）相關(guān)；

而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。

⑧、哈希表

哈希表（Hash Table），也叫散列表，是一種可以通過關(guān)鍵碼值（key-value）直接訪問的數(shù)據(jù)結(jié)構(gòu)，它最大的特點(diǎn)就是可以快速實(shí)現(xiàn)查找、插入和刪除。

數(shù)組的最大特點(diǎn)就是查找容易，插入和刪除困難；而鏈表正好相反，查找困難，而插入和刪除容易。哈希表很完美地結(jié)合了兩者的優(yōu)點(diǎn)， Java 的 HashMap 在此基礎(chǔ)上還加入了樹的優(yōu)點(diǎn)。

 

哈希函數(shù)在哈希表中起著?常關(guān)鍵的作?，它可以把任意長度的輸入變換成固定長度的輸出，該輸出就是哈希值。哈希函數(shù)使得一個(gè)數(shù)據(jù)序列的訪問過程變得更加迅速有效，通過哈希函數(shù)，數(shù)據(jù)元素能夠被很快的進(jìn)行定位。

若關(guān)鍵字為 k，則其值存放在 hash(k) 的存儲位置上。由此，不需要遍歷就可以直接取得 k 對應(yīng)的值。

對于任意兩個(gè)不同的數(shù)據(jù)塊，其哈希值相同的可能性極小，也就是說，對于一個(gè)給定的數(shù)據(jù)塊，找到和它哈希值相同的數(shù)據(jù)塊極為困難。再者，對于一個(gè)數(shù)據(jù)塊，哪怕只改動它的一個(gè)比特位，其哈希值的改動也會非常的大——這正是 Hash 存在的價(jià)值！

盡管可能性極小，但仍然會發(fā)生，如果哈希沖突了，Java 的 HashMap 會在數(shù)組的同一個(gè)位置上增加鏈表，如果鏈表的長度大于 8，將會轉(zhuǎn)化成紅黑樹進(jìn)行處理——這就是所謂的拉鏈法（數(shù)組+鏈表）。

說句實(shí)在話，照這個(gè)進(jìn)度惡補(bǔ)下去，我感覺要禿的節(jié)奏，不過，如果能夠變得更強(qiáng)，值了——對，值了。