Java數(shù)據(jù)結構
要理解Java數(shù)據(jù)結構，必須能清楚何為數(shù)據(jù)結構?
數(shù)據(jù)結構：
Data_Structure，它是儲存數(shù)據(jù)的一種結構體，在此結構中儲存一些數(shù)據(jù)，而這些數(shù)據(jù)之間有一定的關系。
而各數(shù)據(jù)元素之間的相互關系，又包括三個組成成分，數(shù)據(jù)的邏輯結構，數(shù)據(jù)的存儲結構和數(shù)據(jù)運算結構。
而一個數(shù)據(jù)結構的設計過程分成抽象層、數(shù)據(jù)結構層和實現(xiàn)層。
數(shù)據(jù)結構在Java的語言體系中按邏輯結構可以分為兩大類：線性數(shù)據(jù)結構和非線性數(shù)據(jù)結構。
一、Java數(shù)據(jù)結構之：線性數(shù)據(jù)結構
線性數(shù)據(jù)結構：常見的有一維數(shù)組，線性表，棧，隊列，雙隊列，串。
1、一維數(shù)組在Java里面常用的util有：String []，int []，ArrayList，Vector，CopyOnWriteArrayList等，及可以通過一維數(shù)組[]自己實現(xiàn)不同邏輯結構的Util類，而ArrayList封裝了一些[]的基本操作方法。
ArrayList和Vector的區(qū)別是：Vector是線程安全的，方法同步。CopyOnWriteArrayList也是線程安全的但效率要比Vector高很多。
數(shù)組這種數(shù)據(jù)結構典型的操作方法，是根據(jù)下標進行操作的，所以insert的的時候可以根據(jù)下標插入到具體的某個位置，但是這個時候它后面的元素都得往后面移動一位。所以插入效率比較低,更新，刪除效率也比較低，而查詢效率非常高,查詢效率時間復雜度是1。
2、線性表
線性表是有序的儲存結構、鏈式的儲存結構。鏈表的物理儲存空間是不連續(xù)的，鏈表的每一個節(jié)點都知道上一個節(jié)點、或者下一個節(jié)點是誰，通常用Node表示。常見的有順序鏈表(linkedList、linked***)，單項鏈表(里面只有Node類)，雙向鏈表(兩個Node類)，循環(huán)鏈表(多個Node類)等。
操作方法：插入效率比較高，插入的時候只需要改變節(jié)點的前后節(jié)點的連接即可。而查詢效率就比較低了，如果實現(xiàn)的不好，需要整個鏈路找下去才能找到應該找的元素。所以常見的方法有：add(index,element)，addFirst(element)，addLast(element)，getFirst()，getLast()，get(element)等。
常見的Uitil有：linkedList，linkedMap等，而這兩個JDK底層也做了N多優(yōu)化，可以有效避免查詢效率低的問題，當自己實現(xiàn)的時候需要注意。其實樹形結構可以說是非線性的鏈式儲存結構。
3、棧Stack
棧最主要的是要實現(xiàn)先進后出，后進先出的邏輯結構。來實現(xiàn)一些場景對邏輯順序的要求。所以常用的方法有push(element)壓棧，pop()出棧。
java.util.Stack就實現(xiàn)了這用邏輯，而Java的Jvm里面也用的到了此種數(shù)據(jù)結構，就是線程棧，來保證當前線程的執(zhí)行順序。
4、隊列
隊列，隊列是一種特殊的線性數(shù)據(jù)結構，隊列只能允許在隊頭，隊尾進行添加和查詢等相關操作。隊列又有單項有序隊列、雙向隊列、阻塞隊列等。
Queue這種數(shù)據(jù)結構注定了基本操作方法有：add(E e)加入隊列，remove(),poll()等方法。隊列在Java語言環(huán)境中是使用頻率相當高的數(shù)據(jù)結構，所有其實現(xiàn)的類也很多來滿足不同場景。
使用場景也非常多，如線程池、MQ、連接池等。
5、串串：也稱字符串，是由N個字符組成的優(yōu)先序列。在Java里面就是指String，而String里面是由chat[]來進行儲存。
KMP算法： 這個算法一定要牢記，Java數(shù)據(jù)結構這本書里面針對字符串的查找匹配算法也只介紹了一種。關鍵點就是：在字符串比對的時候，主串的比較位置不需要回退的問題。
二、Java數(shù)據(jù)結構之：非線性數(shù)據(jù)結構
非線性數(shù)據(jù)結構：常見的有：多維數(shù)組，集合，樹，圖，散列表(hash)。
1、多維數(shù)組一維數(shù)組前面咱也提到了，多維數(shù)組無非就是String [][]，int[][]等。Java里面很少提供這樣的工具類，而Java里面tree和圖底層的native方法用了多維數(shù)組來儲存。2、集合由一個或多個確定的元素所構成的整體叫做集合，在Java里面可以去廣義的去理解為實現(xiàn)了Collection接口的類都叫集合。
3、樹
樹形結構，作者覺得它是一種特殊的鏈形數(shù)據(jù)結構。最少有一個根節(jié)點組成，可以有多個子節(jié)點。樹，顯然是由遞歸算法組成。
樹的特點：
在一個樹結構中，有且僅有一個結點沒有直接父節(jié)點，它就是根節(jié)點;
除了根節(jié)點，其他結點有且只有一個直接父節(jié)點;
每個結點可以有任意多個直接子節(jié)點。
樹的數(shù)據(jù)結構又分如下幾種：
1) 自由樹/普通樹：對子節(jié)點沒有任何約束。
2) 二叉樹：每個節(jié)點最多含有兩個子節(jié)點的樹稱為二叉樹。2.1) 一般二叉樹：每個子節(jié)點的父親節(jié)點不一定有兩個子節(jié)點的二叉樹成為一般二叉樹。2.2) 完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹;2.3) 滿二叉樹：所有的節(jié)點都是二叉的二叉樹成為滿二叉樹。
3) 二叉搜索樹/BST：binary search tree,又稱二叉排序樹、二叉查找樹。是有序的。要點：如果不為空，那么其左子樹節(jié)點的值都小于根節(jié)點的值;右子樹節(jié)點的值都大于根節(jié)點的值。
3.1) 二叉平衡樹：二叉搜索樹，是有序的排序樹，但左右兩邊包括子節(jié)點不一定平衡，而二叉平衡樹是排序樹的一種，并且加點條件，就是任意一個節(jié)點的兩個叉的深度差不多(比如差值的絕對值小于某個常數(shù)，或者一個不能比另一個深出去一倍之類的)。這樣的樹可以保證二分搜索任意元素都是O(log n)的，一般還附帶帶有插入或者刪除某個元素也是O(log n)的的性質。
為了實現(xiàn)，二叉平衡樹又延伸出來了一些算法，業(yè)界常見的有AVL、和紅黑算法，所以又有以下兩種樹：
3.1.1) AVL樹：最早的平衡二叉樹之一。應用相對其他數(shù)據(jù)結構比較少。windows對進程地址空間的管理用到了AVL樹。
3.1.2) 紅黑樹：通過制定了一些紅黑標記和左右旋轉規(guī)則來保證二叉樹平衡。
紅黑樹的5條性質：
每個結點要么是紅的，要么是黑的。
根結點是黑的。
每個葉結點(葉結點即指樹尾端NIL指針或NULL結點)是黑的。
如果一個結點是紅的，那么它的倆個兒子都是黑的。
對于任一結點而言，其到葉結點樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結點。
4) B-tree：又稱B樹、B-樹。又叫平衡(balance)多路查找樹。樹中每個結點最多含有m個孩子(m>=2)。它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節(jié)點有更多的子節(jié)點。
4) B+tree：又稱B+。是B-樹的變體，也是一種多路搜索樹。
樹總結： 樹在Java里面應用的也比較多。非排序樹，主要用來做數(shù)據(jù)儲存和展示。而排序樹，主要用來做算法和運算，HashMap里面的TreeNode就用到了紅黑樹算法。而B+樹在數(shù)據(jù)庫的索引原理里面有典型的應用。
以上就是長沙中公優(yōu)就業(yè)Java培訓機構小編介紹的“如何徹底搞懂 Java 數(shù)據(jù)結構？”的內容，希望對大家有幫助，如有疑問，請在線咨詢，有專業(yè)老師隨時為你服務。
相關文章
零基礎怎么自學Java，完整版Java學習路線圖
你還在糾結學Java，是自學還是去培訓班嗎
一個標準的Java程序員如何進階?
Java學習路線清單，快速進階Java
Java編程初學者要如何進階
