java常用數(shù)據(jù)結(jié)構(gòu)是什么

這篇文章將為大家詳細講解有關(guān)java常用數(shù)據(jù)結(jié)構(gòu)是什么，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

公司主營業(yè)務(wù)：網(wǎng)站設(shè)計、成都網(wǎng)站設(shè)計、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)公司是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)公司推出扎蘭屯免費做網(wǎng)站回饋大家。

java數(shù)據(jù)結(jié)構(gòu)有：1、數(shù)組；2、鏈表，一種遞歸的數(shù)據(jù)結(jié)構(gòu)；3、棧，按照“后進先出”、“先進后出”的原則來存儲數(shù)據(jù)；4、隊列；5、樹，是由 n（n>0）個有限節(jié)點組成的一個具有層次關(guān)系的集合；6、堆；7、圖；8、哈希表。

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

Java常見數(shù)據(jù)結(jié)構(gòu)

這 8 種數(shù)據(jù)結(jié)構(gòu)有什么區(qū)別呢？

①、數(shù)組

優(yōu)點：

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

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

缺點：

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

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

添加、刪除元素的操作很耗時間，因為要移動其他元素。

②、鏈表

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

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

  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。

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

優(yōu)點：

• 不需要初始化容量；

• 可以添加任意元素；

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

缺點：

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

• 查找元素需要遍歷整個鏈表，耗時。

③、棧

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

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

④、隊列

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

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

⑤、樹

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

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

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

• 沒有父節(jié)點的節(jié)點稱為根節(jié)點；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑥、堆

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

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

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

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

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

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

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

⑧、哈希表

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

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

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

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

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

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

關(guān)于“java常用數(shù)據(jù)結(jié)構(gòu)是什么”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

新聞標題：java常用數(shù)據(jù)結(jié)構(gòu)是什么
鏈接地址：http://muchs.cn/article34/iepese.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站建設(shè)、微信公眾號、用戶體驗、ChatGPT、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)