Java數據結構

　　要理解Java數據結構，必須能清楚何為數據結構?

　　數據結構：

　　Data_Structure，它是儲存數據的一種結構體，在此結構中儲存一些數據，而這些數據之間有一定的關系。

　　而各數據元素之間的相互關系，又包括三個組成成分，數據的邏輯結構，數據的存儲結構和數據運算結構。

　　而一個數據結構的設計過程分成抽象層、數據結構層和實現層。

　　數據結構在Java的語言體系中按邏輯結構可以分為兩大類：線性數據結構和非線性數據結構。

　　一、Java數據結構之：線性數據結構

　　線性數據結構：常見的有一維數組，線性表，棧，隊列，雙隊列，串。

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

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

       數組這種數據結構典型的操作方法，是根據下標進行操作的，所以insert的的時候可以根據下標插入到具體的某個位置，但是這個時候它后面的元素都得往后面移動一位。所以插入效率比較低,更新，刪除效率也比較低，而查詢效率非常高,查詢效率時間復雜度是1。

       2、線性表

       線性表是有序的儲存結構、鏈式的儲存結構。鏈表的物理儲存空間是不連續的，鏈表的每一個節點都知道上一個節點、或者下一個節點是誰，通常用Node表示。常見的有順序鏈表(LinkedList、Linked***)，單項鏈表(里面只有Node類)，雙向鏈表(兩個Node類)，循環鏈表(多個Node類)等。

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

       常見的Uitil有：LinkedList，LinkedMap等，而這兩個JDK底層也做了N多優化，可以有效避免查詢效率低的問題，當自己實現的時候需要注意。其實樹形結構可以說是非線性的鏈式儲存結構。  

       3、棧Stack

       棧最主要的是要實現先進后出，后進先出的邏輯結構。來實現一些場景對邏輯順序的要求。所以常用的方法有push(element)壓棧，pop()出棧。

       java.util.Stack就實現了這用邏輯，而Java的Jvm里面也用的到了此種數據結構，就是線程棧，來保證當前線程的執行順序。

      4、隊列

      隊列，隊列是一種特殊的線性數據結構，隊列只能允許在隊頭，隊尾進行添加和查詢等相關操作。隊列又有單項有序隊列、雙向隊列、阻塞隊列等。

      Queue這種數據結構注定了基本操作方法有：add(E e)加入隊列，remove(),poll()等方法。隊列在Java語言環境中是使用頻率相當高的數據結構，所有其實現的類也很多來滿足不同場景。

　　使用場景也非常多，如線程池、MQ、連接池等。

　　5、串串：也稱字符串，是由N個字符組成的優先序列。在Java里面就是指String，而String里面是由chat[]來進行儲存。

　　KMP算法： 這個算法一定要牢記，Java數據結構這本書里面針對字符串的查找匹配算法也只介紹了一種。關鍵點就是：在字符串比對的時候，主串的比較位置不需要回退的問題。

　　二、Java數據結構之：非線性數據結構

　　非線性數據結構：常見的有：多維數組，集合，樹，圖，散列表(hash)。

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

       3、樹

　　樹形結構，作者覺得它是一種特殊的鏈形數據結構。最少有一個根節點組成，可以有多個子節點。樹，顯然是由遞歸算法組成。

　　樹的特點：

　　在一個樹結構中，有且僅有一個結點沒有直接父節點，它就是根節點;

　　除了根節點，其他結點有且只有一個直接父節點;

　　每個結點可以有任意多個直接子節點。

　　樹的數據結構又分如下幾種：

　　1) 自由樹/普通樹：對子節點沒有任何約束。

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

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

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

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

      3.1.1) AVL樹：最早的平衡二叉樹之一。應用相對其他數據結構比較少。windows對進程地址空間的管理用到了AVL樹。

      3.1.2) 紅黑樹：通過制定了一些紅黑標記和左右旋轉規則來保證二叉樹平衡。

　　紅黑樹的5條性質：

　　每個結點要么是紅的，要么是黑的。

　　根結點是黑的。

　　每個葉結點(葉結點即指樹尾端NIL指針或NULL結點)是黑的。

　　如果一個結點是紅的，那么它的倆個兒子都是黑的。

　　對于任一結點而言，其到葉結點樹尾端NIL指針的每一條路徑都包含相同數目的黑結點。

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

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

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

       以上就是動力節點Java培訓機構小編介紹的“如何徹底搞懂 Java 數據結構？”的內容，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為你服務。

       相關文章

　　零基礎怎么自學Java，完整版Java學習路線圖

　　你還在糾結學Java，是自學還是去培訓班嗎

　　一個標準的Java程序員如何進階?

　　Java學習路線清單，快速進階Java

　　Java編程初學者要如何進階