java資料結(jié)構(gòu)有：1、陣列；2、鍊錶，一種遞歸的資料結(jié)構(gòu)；3、棧，依照「後進(jìn)先出」、「先進(jìn)後出」的原則來儲存資料；4、隊(duì)列；5、樹，是由n（n>0）個有限節(jié)點(diǎn)組成的一個具有層次關(guān)係的集合；6、堆；7、圖；8、哈希表。

本教學(xué)操作環(huán)境：windows7系統(tǒng)、java8版、DELL G3電腦。

Java常見資料結(jié)構(gòu)

#這 8 種資料結(jié)構(gòu)有什麼差別呢？

①、陣列

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

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

• 依照索引遍歷陣列也很方便。

缺點(diǎn)：

• 陣列的大小在建立後就確定了，無法擴(kuò)容；

• 陣列只能儲存一種類型的資料；

新增、刪除元素的操作很耗時間，因?yàn)橐苿悠渌亍?

②、鍊錶

• #《演算法（第4 版）》一書中是這樣定義鍊錶的：

  鍊錶是一種遞歸的資料結(jié)構(gòu)，它或是為空（null），或是指向一個結(jié)點(diǎn)（node）的引用，該節(jié)點(diǎn)還有一個元素和一個指向另一個鍊錶的引用。

  Java 的LinkedList 類別可以很形像地透過程式碼的形式來表示一個鍊錶的結(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;
        }
    }
}

• 這是一種雙向鍊錶，目前元素item 既有prev 又有next，不過first 的prev 為null，last 的next 為null。如果是單向鍊錶的話，就只有 next，沒有 prev。

由於不必按照順序的方式存儲，鍊錶在插入、刪除的時候可以達(dá)到O(1) 的時間複雜度（只需要重新指向引用即可，不需要像陣列那樣移動其他元素）。除此之外，鍊錶也克服了陣列必須預(yù)先知道資料大小的缺點(diǎn)，從而可以實(shí)現(xiàn)靈活的記憶體動態(tài)管理。

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

• 不需要初始化容量；

• 可以加入任意元素；

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

缺點(diǎn)：

• 含有大量的引用，佔(zhàn)用的記憶體空間大；

• 查找元素需要遍歷整個鍊錶，耗時。

③、堆疊

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

同理，堆疊依照「後進(jìn)先出」、「先進(jìn)後出」的原則來儲存數(shù)據(jù)，先插入的數(shù)據(jù)被壓入棧底，後插入的數(shù)據(jù)在棧頂，讀出數(shù)據(jù)的時候，從棧頂開始依序讀出。

④、佇列

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

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

⑤、樹

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

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

• 每個節(jié)點(diǎn)都只有有限個子節(jié)點(diǎn)或無子節(jié)點(diǎn)；

• ##沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

• 每一個非根節(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)；

• 除了根節(jié)點(diǎn)外，每個子節(jié)點(diǎn)可分為多個不相交的子樹。

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

?

#?

?

?

基於二元查找樹的特點(diǎn)，它相比較於其他資料結(jié)構(gòu)的優(yōu)勢就在於尋找、插入的時間複雜度較低，為O(logn)。假如我們要從上圖找5 個元素，先從根節(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)演化的情況，所以對二叉搜尋樹中每個節(jié)點(diǎn)的左右子樹作了限制，左右子樹的高度差稱為平衡因子，樹中每個節(jié)點(diǎn)的平衡因子絕對值不大於1。

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

Java 中最常見的平衡二元樹是紅黑樹，節(jié)點(diǎn)是紅色或黑色，透過顏色的限制來維持著二元樹的平衡：

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

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

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

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

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

?

⑥、堆

#堆可以被看做是一棵樹的陣列對象，具有以下特點(diǎn)：

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

• ##堆總是一棵完全二元樹。

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

?

?

在線性結(jié)構(gòu)中，資料元素之間滿足唯一的線性關(guān)係，每個資料元素（除第一個和最後一個外）均有唯一的「前驅(qū)」與「後繼」；

在樹狀結(jié)構(gòu)中，資料元素之間有著明顯的層次關(guān)係，且每個資料元素只與上一層中的一個元素（父節(jié)點(diǎn)）及下一層的多個元素（子節(jié)點(diǎn)）相關(guān)；

而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)係是任意的，圖中任兩個資料元素之間都有可能相關(guān)。

⑧、哈希表

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

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

?

#雜湊函數(shù)在雜湊表中起?常關(guān)鍵的作?，它可以把任意長度的輸入轉(zhuǎn)換成固定長度的輸出，該輸出就是哈希值。雜湊函數(shù)使得一個資料序列的存取過程變得更加迅速有效，透過雜湊函數(shù)，資料元素能夠被很快的進(jìn)行定位。

若關(guān)鍵字為 k，則其值存放在?

hash(k)?的儲存位置。由此，不需要遍歷就可以直接取得 k 對應(yīng)的值。

對於任意兩個不同的資料區(qū)塊，其雜湊值相同的可能性極小，也就是說，對於一個給定的資料區(qū)塊，找到和它雜湊值相同的資料區(qū)塊極為困難。再者，對於一個資料區(qū)塊，即使只改動它的一個位元，其雜湊值的改變也會非常的大——這正是 Hash 存在的價值！

儘管可能性極小，但仍然會發(fā)生，如果雜湊衝突了，Java 的HashMap 會在陣列的同一個位置上增加鍊錶，如果鍊錶的長度大於8，將會轉(zhuǎn)換成紅黑樹進(jìn)行處理－這就是所謂的拉鍊法（陣列鍊錶）。

更多程式相關(guān)知識，請?jiān)煸L：程式設(shè)計(jì)影片！ ！

以上是java常用資料結(jié)構(gòu)有哪些的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！