本篇內(nèi)容介紹了“Java線性數(shù)據(jù)結(jié)構(gòu)是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
在荊州等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需制作網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站建設(shè),全網(wǎng)營(yíng)銷推廣,成都外貿(mào)網(wǎng)站制作,荊州網(wǎng)站建設(shè)費(fèi)用合理。
一眼看上去就知道的，像 String []、int [] 這種；還有需要看兩眼才能看透的（看源碼了），像 ArrayList，內(nèi)部對(duì)數(shù)組進(jìn)行了封裝。
數(shù)組這種數(shù)據(jù)結(jié)構(gòu)最大的好處，就是可以根據(jù)下標(biāo)（或者叫索引）進(jìn)行操作，插入的時(shí)候可以根據(jù)下標(biāo)直接插入到具體的位置，但與此同時(shí)，后面的元素就需要全部向后移動(dòng)，需要移動(dòng)的數(shù)據(jù)越多，就越累。
假設(shè)現(xiàn)在已經(jīng)有了一個(gè) ArrayList 了，準(zhǔn)備在第 4 個(gè)位置（下標(biāo)為 3）上添加一個(gè)元素 55。
此時(shí) ArrayList 中第 5 個(gè)位置以后的元素將會(huì)向后移動(dòng)。
準(zhǔn)備把 23 從 ArrayList 中移除。
此時(shí)下標(biāo)為 7、8、9 的元素往前挪。
簡(jiǎn)單總結(jié)一下 ArrayList 的時(shí)間復(fù)雜度，方便大家在學(xué)習(xí)的時(shí)候作為參考。
1、通過下標(biāo)（也就是 get(int index)）訪問一個(gè)元素的時(shí)間復(fù)雜度為 O(1)，因?yàn)槭侵边_(dá)的，無論數(shù)據(jù)增大多少倍，耗時(shí)都不變。
2、添加一個(gè)元素（也就是 add()）的時(shí)間復(fù)雜度為 O(1)，因?yàn)橹苯犹砑拥侥┪病?/p>
3、刪除一個(gè)元素的時(shí)間復(fù)雜度為 O(n)，因?yàn)橐闅v列表，數(shù)據(jù)量增大幾倍，耗時(shí)也增大幾倍。
4、查找一個(gè)未排序的列表時(shí)間復(fù)雜度為 O(n)，因?yàn)橐闅v列表；查找排序過的列表時(shí)間復(fù)雜度為 O(log n)，因?yàn)榭梢允褂枚植檎曳ǎ?dāng)數(shù)據(jù)增大 n 倍時(shí)，耗時(shí)增大 logn 倍（這里的 log 是以 2 為底的，每找一次排除一半的可能）。
鏈表在物理存儲(chǔ)空間是不連續(xù)的，但每個(gè)節(jié)點(diǎn)要么知道它的下一個(gè)節(jié)點(diǎn)是誰，要么知道它的上一個(gè)節(jié)點(diǎn)是誰，仿佛就像我們之間隔著千山萬水，卻心有靈犀一點(diǎn)鏈。像 LinkedList 就是最典型的鏈表結(jié)構(gòu)，通過引用相互鏈接。
LinkedList 中的每一個(gè)元素都可以稱之為節(jié)點(diǎn)（Node），每一個(gè)節(jié)點(diǎn)都包含三個(gè)項(xiàng)目：其一是元素本身，其二是指向下一個(gè)元素的引用地址，其三是指向上一個(gè)元素的引用地址。
LinkedList 看起來就像下面這個(gè)樣子：
第一個(gè)節(jié)點(diǎn)由于沒有前一個(gè)節(jié)點(diǎn)，所以 prev 為 null；
最后一個(gè)節(jié)點(diǎn)由于沒有后一個(gè)節(jié)點(diǎn)，所以 next 為 null；
這是一個(gè)雙向鏈表，每一個(gè)節(jié)點(diǎn)都由三部分組成，前后節(jié)點(diǎn)和值。
相比 ArrayList，LinkedList 有以下優(yōu)勢(shì)：
1、LinkedList 允許內(nèi)存進(jìn)行動(dòng)態(tài)分配，這就意味著內(nèi)存分配是由編譯器在運(yùn)行時(shí)完成的，我們無需在 LinkedList 聲明的時(shí)候指定大小。
2、LinkedList 不需要在連續(xù)的位置上存儲(chǔ)元素，因?yàn)楣?jié)點(diǎn)可以通過引用指定下一個(gè)節(jié)點(diǎn)或者前一個(gè)節(jié)點(diǎn)。也就是說，LinkedList 在插入和刪除元素的時(shí)候代價(jià)很低，因?yàn)椴恍枰苿?dòng)其他元素，只需要更新前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的引用地址即可。
棧是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它就像一摞盤子，第一個(gè)放在最下面，第二個(gè)放在第一個(gè)上面，第三個(gè)放在第二個(gè)上面，最后一個(gè)放在最上面。棧遵循后進(jìn)先出的原則，也就是“Last In First Out”（簡(jiǎn)稱 LIFO）——最后的一個(gè)進(jìn)的，最先出去。
對(duì)于棧這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)來說，它有兩個(gè)常見的動(dòng)作：
push，中文釋義有很多種，我個(gè)人更喜歡叫它“壓入”，非常形象。當(dāng)我們要把一個(gè)數(shù)據(jù)放入棧的頂部，這個(gè)動(dòng)作就叫做 push。
pop，同樣的，我個(gè)人更喜歡叫它“彈出”，帶有很強(qiáng)烈的動(dòng)畫效果，有沒有？當(dāng)我們要從棧中移除一個(gè)數(shù)據(jù)時(shí)，這個(gè)動(dòng)作就叫做 pop。
隊(duì)列，只允許在隊(duì)尾添加數(shù)據(jù)，隊(duì)首移除數(shù)據(jù)。隊(duì)列在 Java 中的出現(xiàn)頻率非常高，有各種不同的類來滿足不同的場(chǎng)景需求。像優(yōu)先級(jí)隊(duì)列 PriorityQueue、延時(shí)隊(duì)列 DelayQueue 等等。隊(duì)列遵循的是 First In First Out，縮寫為 FIFO，也就是先進(jìn)先出，第一個(gè)進(jìn)入隊(duì)列的第一個(gè)先出來。
再來說非線性數(shù)據(jù)結(jié)構(gòu)。
樹是一種典型的非線性結(jié)構(gòu)，它是由 n（n>0）個(gè)有限節(jié)點(diǎn)組成的一個(gè)具有層次關(guān)系的集合。之所以叫“樹”，是因?yàn)檫@種數(shù)據(jù)結(jié)構(gòu)看起來就像是一個(gè)倒掛的樹，只不過根在上，葉在下。樹形數(shù)據(jù)結(jié)構(gòu)有以下這些特點(diǎn)：
每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無子節(jié)點(diǎn)；
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹。
下圖展示了樹的一些術(shù)語：
根節(jié)點(diǎn)是第 0 層，它的子節(jié)點(diǎn)是第 1 層，子節(jié)點(diǎn)的子節(jié)點(diǎn)為第 2 層，以此類推。
深度：對(duì)于任意節(jié)點(diǎn) n，n 的深度為從根到 n 的唯一路徑長(zhǎng)，根的深度為 0。
高度：對(duì)于任意節(jié)點(diǎn) n，n 的高度為從 n 到一片樹葉的最長(zhǎng)路徑長(zhǎng)，所有樹葉的高度為 0。
樹又可以細(xì)分為下面幾種：
1、普通樹：對(duì)子節(jié)點(diǎn)沒有任何約束。
2、二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子節(jié)點(diǎn)的樹。 二叉樹按照不同的表現(xià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)數(shù)都達(dá)到了最大值的二叉樹。有兩種表現(xiàn)形式，第一種，像下圖這樣（每一層都是滿的），滿足每一層的節(jié)點(diǎn)數(shù)都達(dá)到了最大值 2。
3、二叉查找樹：英文名叫 Binary Search Tree，即 BST，需要滿足以下條件：
任意節(jié)點(diǎn)的左子樹不空，左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
任意節(jié)點(diǎn)的右子樹不空，右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。
3.1、平衡二叉樹：當(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)演化的情況，所以對(duì)二叉搜索樹中每個(gè)節(jié)點(diǎn)的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個(gè)節(jié)點(diǎn)的平衡因子絕對(duì)值不大于 1。
平衡二叉樹的難點(diǎn)在于，當(dāng)刪除或者增加節(jié)點(diǎn)的情況下，如何通過左旋或者右旋的方式來保持左右平衡。
紅黑樹是一種常見的平衡二叉樹，節(jié)點(diǎn)是紅色或者黑色，通過顏色的約束來維持著二叉樹的平衡：
每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色
根節(jié)點(diǎn)是黑色
每個(gè)葉節(jié)點(diǎn)（NIL 節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。
如果一個(gè)節(jié)點(diǎn)是紅色的，則它兩個(gè)子節(jié)點(diǎn)都是黑色的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色節(jié)點(diǎn)。
從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
4、B 樹：一種對(duì)讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多于兩個(gè)的子樹。
5、B+ 樹：B 樹的變體。
HashMap 里面的 TreeNode 就用到了紅黑樹，而 B 樹、B+ 樹在數(shù)據(jù)庫的索引原理里面有典型的應(yīng)用。
哈希表（Hash Table），也叫散列表，是一種可以通過關(guān)鍵碼值（key-value）直接訪問的數(shù)據(jù)結(jié)構(gòu)，它最大的特點(diǎn)就是可以快速實(shí)現(xiàn)查找、插入和刪除。其中用到的算法叫做哈希，就是把任意長(zhǎng)度的輸入，變換成固定長(zhǎng)度的輸出，該輸出就是哈希值。像 MD5、SHA1 都用的是哈希算法。
每一個(gè) Java 對(duì)象都會(huì)有一個(gè)哈希值，默認(rèn)情況就是通過調(diào)用本地方法執(zhí)行哈希算法，計(jì)算出對(duì)象的內(nèi)存地址 + 對(duì)象的值的關(guān)鍵碼值。
數(shù)組的最大特點(diǎn)就是查找容易，插入和刪除困難；而鏈表正好相反，查找困難，而插入和刪除容易。哈希表很完美地結(jié)合了兩者的優(yōu)點(diǎn)， Java 的 HashMap 在此基礎(chǔ)上還加入了樹的優(yōu)點(diǎn)。
哈希表具有較快（常量級(jí)）的查詢速度，以及相對(duì)較快的增刪速度，所以很適合在海量數(shù)據(jù)的環(huán)境中使用。
對(duì)于任意兩個(gè)不同的數(shù)據(jù)塊，其哈希值相同的可能性極小，也就是說，對(duì)于一個(gè)給定的數(shù)據(jù)塊，找到和它哈希值相同的數(shù)據(jù)塊極為困難。再者，對(duì)于一個(gè)數(shù)據(jù)塊，哪怕只改動(dòng)它的一個(gè)比特位，其哈希值的改動(dòng)也會(huì)非常的大——這正是 Hash 存在的價(jià)值！
盡管可能性極小，但仍然會(huì)發(fā)生，如果哈希沖突了，Java 的 HashMap 會(huì)在數(shù)組的同一個(gè)位置上增加鏈表，如果鏈表的長(zhǎng)度大于 8，將會(huì)轉(zhuǎn)化成紅黑樹進(jìn)行處理——這就是所謂的拉鏈法（數(shù)組+鏈表）。
圖是一種復(fù)雜的非線性結(jié)構(gòu)，由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G（V，E），其中，G 表示一個(gè)圖，V 是圖 G 中頂點(diǎn)的集合，E 是圖 G 中邊的集合。
上圖共有 V0，V1，V2，V3 這 4 個(gè)頂點(diǎn)，4 個(gè)頂點(diǎn)之間共有 5 條邊。
在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間滿足唯一的線性關(guān)系，每個(gè)數(shù)據(jù)元素（除第一個(gè)和最后一個(gè)外）均有唯一的“前驅(qū)”和“后繼”；
在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每個(gè)數(shù)據(jù)元素只與上一層中的一個(gè)元素（父節(jié)點(diǎn)）及下一層的多個(gè)元素（子節(jié)點(diǎn)）相關(guān)；
而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。
“Java線性數(shù)據(jù)結(jié)構(gòu)是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
重慶分公司
重慶分公司
