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

　　要理解Java數(shù)據(jù)結(jié)構(gòu)，必須能清楚何為數(shù)據(jù)結(jié)構(gòu)?

　　數(shù)據(jù)結(jié)構(gòu)：

　　Data_Structure，它是儲(chǔ)存數(shù)據(jù)的一種結(jié)構(gòu)體，在此結(jié)構(gòu)中儲(chǔ)存一些數(shù)據(jù)，而這些數(shù)據(jù)之間有一定的關(guān)系。

　　而各數(shù)據(jù)元素之間的相互關(guān)系，又包括三個(gè)組成成分，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算結(jié)構(gòu)。

　　而一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。

　　數(shù)據(jù)結(jié)構(gòu)在Java的語言體系中按邏輯結(jié)構(gòu)可以分為兩大類：線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。

　　一、Java數(shù)據(jù)結(jié)構(gòu)之：線性數(shù)據(jù)結(jié)構(gòu)

　　線性數(shù)據(jù)結(jié)構(gòu)：常見的有一維數(shù)組，線性表，棧，隊(duì)列，雙隊(duì)列，串。

　　1、一維數(shù)組在Java里面常用的util有：String []，int []，ArrayList，Vector，CopyOnWriteArrayList等，及可以通過一維數(shù)組[]自己實(shí)現(xiàn)不同邏輯結(jié)構(gòu)的Util類，而ArrayList封裝了一些[]的基本操作方法。

       ArrayList和Vector的區(qū)別是：Vector是線程安全的，方法同步。CopyOnWriteArrayList也是線程安全的但效率要比Vector高很多。

       數(shù)組這種數(shù)據(jù)結(jié)構(gòu)典型的操作方法，是根據(jù)下標(biāo)進(jìn)行操作的，所以insert的的時(shí)候可以根據(jù)下標(biāo)插入到具體的某個(gè)位置，但是這個(gè)時(shí)候它后面的元素都得往后面移動(dòng)一位。所以插入效率比較低,更新，刪除效率也比較低，而查詢效率非常高,查詢效率時(shí)間復(fù)雜度是1。

       2、線性表

       線性表是有序的儲(chǔ)存結(jié)構(gòu)、鏈?zhǔn)降膬?chǔ)存結(jié)構(gòu)。鏈表的物理儲(chǔ)存空間是不連續(xù)的，鏈表的每一個(gè)節(jié)點(diǎn)都知道上一個(gè)節(jié)點(diǎn)、或者下一個(gè)節(jié)點(diǎn)是誰，通常用Node表示。常見的有順序鏈表(LinkedList、Linked***)，單項(xiàng)鏈表(里面只有Node類)，雙向鏈表(兩個(gè)Node類)，循環(huán)鏈表(多個(gè)Node類)等。

       操作方法：插入效率比較高，插入的時(shí)候只需要改變節(jié)點(diǎn)的前后節(jié)點(diǎn)的連接即可。而查詢效率就比較低了，如果實(shí)現(xiàn)的不好，需要整個(gè)鏈路找下去才能找到應(yīng)該找的元素。所以常見的方法有：add(index,element)，addFirst(element)，addLast(element)，getFirst()，getLast()，get(element)等。

       常見的Uitil有：LinkedList，LinkedMap等，而這兩個(gè)JDK底層也做了N多優(yōu)化，可以有效避免查詢效率低的問題，當(dāng)自己實(shí)現(xiàn)的時(shí)候需要注意。其實(shí)樹形結(jié)構(gòu)可以說是非線性的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)。  

       3、棧Stack

       棧最主要的是要實(shí)現(xiàn)先進(jìn)后出，后進(jìn)先出的邏輯結(jié)構(gòu)。來實(shí)現(xiàn)一些場(chǎng)景對(duì)邏輯順序的要求。所以常用的方法有push(element)壓棧，pop()出棧。

       java.util.Stack就實(shí)現(xiàn)了這用邏輯，而Java的Jvm里面也用的到了此種數(shù)據(jù)結(jié)構(gòu)，就是線程棧，來保證當(dāng)前線程的執(zhí)行順序。

      4、隊(duì)列

      隊(duì)列，隊(duì)列是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，隊(duì)列只能允許在隊(duì)頭，隊(duì)尾進(jìn)行添加和查詢等相關(guān)操作。隊(duì)列又有單項(xiàng)有序隊(duì)列、雙向隊(duì)列、阻塞隊(duì)列等。

      Queue這種數(shù)據(jù)結(jié)構(gòu)注定了基本操作方法有：add(E e)加入隊(duì)列，remove(),poll()等方法。隊(duì)列在Java語言環(huán)境中是使用頻率相當(dāng)高的數(shù)據(jù)結(jié)構(gòu)，所有其實(shí)現(xiàn)的類也很多來滿足不同場(chǎng)景。

　　使用場(chǎng)景也非常多，如線程池、MQ、連接池等。

　　5、串串：也稱字符串，是由N個(gè)字符組成的優(yōu)先序列。在Java里面就是指String，而String里面是由chat[]來進(jìn)行儲(chǔ)存。

　　KMP算法： 這個(gè)算法一定要牢記，Java數(shù)據(jù)結(jié)構(gòu)這本書里面針對(duì)字符串的查找匹配算法也只介紹了一種。關(guān)鍵點(diǎn)就是：在字符串比對(duì)的時(shí)候，主串的比較位置不需要回退的問題。

　　二、Java數(shù)據(jù)結(jié)構(gòu)之：非線性數(shù)據(jù)結(jié)構(gòu)

　　非線性數(shù)據(jù)結(jié)構(gòu)：常見的有：多維數(shù)組，集合，樹，圖，散列表(hash)。

　　1、多維數(shù)組一維數(shù)組前面咱也提到了，多維數(shù)組無非就是String [][]，int[][]等。Java里面很少提供這樣的工具類，而Java里面tree和圖底層的native方法用了多維數(shù)組來儲(chǔ)存。2、集合由一個(gè)或多個(gè)確定的元素所構(gòu)成的整體叫做集合，在Java里面可以去廣義的去理解為實(shí)現(xiàn)了Collection接口的類都叫集合。

       3、樹

　　樹形結(jié)構(gòu)，作者覺得它是一種特殊的鏈形數(shù)據(jù)結(jié)構(gòu)。最少有一個(gè)根節(jié)點(diǎn)組成，可以有多個(gè)子節(jié)點(diǎn)。樹，顯然是由遞歸算法組成。

　　樹的特點(diǎn)：

　　在一個(gè)樹結(jié)構(gòu)中，有且僅有一個(gè)結(jié)點(diǎn)沒有直接父節(jié)點(diǎn)，它就是根節(jié)點(diǎn);

　　除了根節(jié)點(diǎn)，其他結(jié)點(diǎn)有且只有一個(gè)直接父節(jié)點(diǎn);

　　每個(gè)結(jié)點(diǎn)可以有任意多個(gè)直接子節(jié)點(diǎn)。

　　樹的數(shù)據(jù)結(jié)構(gòu)又分如下幾種：

　　1) 自由樹/普通樹：對(duì)子節(jié)點(diǎn)沒有任何約束。

　　2) 二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子節(jié)點(diǎn)的樹稱為二叉樹。2.1) 一般二叉樹：每個(gè)子節(jié)點(diǎn)的父親節(jié)點(diǎn)不一定有兩個(gè)子節(jié)點(diǎn)的二叉樹成為一般二叉樹。2.2) 完全二叉樹：對(duì)于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹;2.3) 滿二叉樹：所有的節(jié)點(diǎn)都是二叉的二叉樹成為滿二叉樹。

      3) 二叉搜索樹/BST：binary search tree,又稱二叉排序樹、二叉查找樹。是有序的。要點(diǎn)：如果不為空，那么其左子樹節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值;右子樹節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。

      3.1) 二叉平衡樹：二叉搜索樹，是有序的排序樹，但左右兩邊包括子節(jié)點(diǎn)不一定平衡，而二叉平衡樹是排序樹的一種，并且加點(diǎn)條件，就是任意一個(gè)節(jié)點(diǎn)的兩個(gè)叉的深度差不多(比如差值的絕對(duì)值小于某個(gè)常數(shù)，或者一個(gè)不能比另一個(gè)深出去一倍之類的)。這樣的樹可以保證二分搜索任意元素都是O(log n)的，一般還附帶帶有插入或者刪除某個(gè)元素也是O(log n)的的性質(zhì)。

      為了實(shí)現(xiàn)，二叉平衡樹又延伸出來了一些算法，業(yè)界常見的有AVL、和紅黑算法，所以又有以下兩種樹：

      3.1.1) AVL樹：最早的平衡二叉樹之一。應(yīng)用相對(duì)其他數(shù)據(jù)結(jié)構(gòu)比較少。windows對(duì)進(jìn)程地址空間的管理用到了AVL樹。

      3.1.2) 紅黑樹：通過制定了一些紅黑標(biāo)記和左右旋轉(zhuǎn)規(guī)則來保證二叉樹平衡。

　　紅黑樹的5條性質(zhì)：

　　每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。

　　根結(jié)點(diǎn)是黑的。

　　每個(gè)葉結(jié)點(diǎn)(葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn))是黑的。

　　如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。

　　對(duì)于任一結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。

　　4) B-tree：又稱B樹、B-樹。又叫平衡(balance)多路查找樹。樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子(m>=2)。它類似普通的平衡二叉樹，不同的一點(diǎn)是B-樹允許每個(gè)節(jié)點(diǎn)有更多的子節(jié)點(diǎn)。

　　4) B+tree：又稱B+。是B-樹的變體，也是一種多路搜索樹。

　　樹總結(jié)： 樹在Java里面應(yīng)用的也比較多。非排序樹，主要用來做數(shù)據(jù)儲(chǔ)存和展示。而排序樹，主要用來做算法和運(yùn)算，HashMap里面的TreeNode就用到了紅黑樹算法。而B+樹在數(shù)據(jù)庫的索引原理里面有典型的應(yīng)用。

       以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)小編介紹的“如何徹底搞懂 Java 數(shù)據(jù)結(jié)構(gòu)？”的內(nèi)容，希望對(duì)大家有幫助，如有疑問，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。

       相關(guān)文章

　　零基礎(chǔ)怎么自學(xué)Java，完整版Java學(xué)習(xí)路線圖

　　你還在糾結(jié)學(xué)Java，是自學(xué)還是去培訓(xùn)班嗎

　　一個(gè)標(biāo)準(zhǔn)的Java程序員如何進(jìn)階?

　　Java學(xué)習(xí)路線清單，快速進(jìn)階Java

　　Java編程初學(xué)者要如何進(jìn)階