線索樹是什麼儲存結構
大家好，我是王有志。關注
王有志
，回覆
DSA
獲取資料結構和演算法學習資源。
從今天開始就進入到資料結構的部分了，整體分為3個部分：線性表，樹和圖，從認識每種資料結構到它們的高階應用。今天我們先從最簡單的線性表和陣列開始。
什麼是線性表？
線性表是我們工作中最常用的資料結構之一，同時它也是我們接觸到的最簡單的資料結構。
根據操作節點的自由度，我們可以將線性表分為兩大類：
非受限線性表
和
受限線性表
。
非受限線性表：陣列，連結串列
受限線性表：棧，佇列
除此之外，字串也是一種特殊的線性表。
在頻繁的使用過程中，你有沒有思考過什麼是線性表？
我們一起來看下百度百科中
線性表
的定義：
線性表（linear list），是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列。
線性表的概念還是很容易理解的，接著來看點頭疼的：
線性表中的個數n定義為線性表的長度，n=0時稱為空表。在非空表中每個資料元素都有一個確定的位置，如用ai表示資料元素，則i稱為資料元素ai線上性表中的位序。
線性表的相鄰元素之間存在著序偶關係。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個順序表，則表中ai-1領先於ai，ai領先於ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接後繼元素。當i=1，2，…，n-1時，ai有且僅有一個直接後繼，當i=2，3，…，n時，ai有且僅有一個直接前驅。
這些看起來是不是就有些頭疼了？我們舉個簡單的例子，糖葫蘆都吃過吧？如果我說糖葫蘆就是一個線性表呢？
我們來看看糖葫蘆是不是符合線性表的定義：
相同特性的資料元素
：都是山楂；
有限
：總共5個山楂；
序列
：給山楂編上號就是完整的序列。
很多小夥伴可能忘記了序列的特點，
序列存在順序關係（可以是混亂的順序，但是要固定）和排成一列（不會有分支，前後一對一的關係）
。
透過這串糖葫蘆，也給出位序，前驅節點和後繼節點的解釋：
位序
：山楂在籤子上確定位置的編號，就是透過這個編號可以找到指定的山楂；
前驅節點
：以2號山楂為例，排在2號前面的都是前驅節點；
直接前驅節點
：還是2號山楂，排在2號山楂，並且緊挨2號山楂的1號山楂就是直接前驅節點；
後繼節點
：和前驅節點反過來；
直接後繼節點
：和直接前驅節點反過來。
再通俗點解釋，可以用“一根線”穿起來的相同物件（元素），並保持固定順序的就是線性表。
這樣理解起來是不是比定義中的數學符號簡單多了？
陣列
知道了什麼是線性表之後，我們來看線性表中最簡單的資料結構：
陣列
。
還記得我們在
演算法的概念和資料的儲存結構
提到的順序儲存結構嗎？陣列正是使用了順序儲存結構。
另外我們提到過每塊記憶體都有自己的編號。這種順序儲存結構加上記憶體編號，使得陣列具有了強大的
隨機存取
能力。
陣列的優點
陣列最大的優點就是隨機存取的能力，換句話說就是
在資料中查詢指定下標的元素速度非常
快。
因為計算機可以透過一步簡單的計算得到儲存該元素的記憶體地址：
起始地址+下標X型別大小
。
這是不是陣列下標從零開始的原因之一呢？
陣列的缺點
計算機的世界中沒有能解決一切問題的“銀彈”，隨機存取的能力不僅僅給了陣列快速查詢元素的資本，也使得陣列在插入和刪除元素後必須要“整理”記憶體，順序儲存結構。
陣列在插入元素後，為了保持隨機存取的特性，必須要向後移動元素。
陣列在刪除元素後，為了保持隨機存取的特性，必須要向前移動元素。
當然，也並不是全部的插入刪除都要移動元素。最好的情況下，在陣列的尾部插入和刪除元素，不需要移動任何元素，此時的時間複雜度是
。如果是最壞的情況，需要在陣列的頭部插入和刪除元素，則要移動整個陣列，此時的時間複雜度是
。
除了陣列的插入和刪除外，還有一種情況我們不得不考慮，如果我們在插入元素時，緊鄰陣列的記憶體已經被分配了怎麼辦？
陣列的擴容
我們先來看一段程式碼：
這3種建立陣列的程式碼，哪個會有編譯時異常？哪個會有執行時異常？
答案是，都能透過編譯，但是第三種在執行時會丟擲異常。
強制要求建立陣列時進行初始化或者指定陣列大小，是為了能夠給陣列分配合適的記憶體。但是這麼做就帶來另一個問題，
建立陣列時，大小已經固定
，如果想新增更多的元素該怎麼辦？
相信你一定非常熟悉
ArrayList
了吧？
ArrayList正是Java中提供的可動態擴容的陣列，它的底層是Object［］，擴容的方式也非常的“粗暴”，當陣列大小不足時，重新申請記憶體（1。5倍），將原陣列元素複製到新的陣列上，並修改引用。
結語
陣列的內容就到此結束了，僅僅從資料結構的角度來看陣列，還是非常簡單的。
可能很多小夥伴會說，工作中都是使用ArrayList了，陣列要退出舞臺了。
我的想法是，大部分場景選擇ArrayList是沒有任何問題的，在追求極致效能，且沒有插入刪除的場景時，陣列或許會是一個不錯的選擇。
練習
嘗試實現一個動態陣列
1。兩數之和：https：//leetcode-cn。com/problems/two-sum
53。最大子陣列和：https：//leetcode-cn。com/problems/maximum-subarray
88。合併兩個有序陣列：https：//leetcode-cn。com/problems/merge-sorted-array
本篇內容的程式碼倉庫：https：//gitee。com/wyz-A2/DSA
好了，今天就到這裡了，Bye~~
參考連結
線性表定義
https：//baike。baidu。com/item/%E7%BA%BF%E6%80%A7%E8%A1%A8/3228081
序列定義
https：//baike。baidu。com/item/%E5%BA%8F%E5%88%97/1302588
陣列定義
https：//baike。baidu。com/item/%E6%95%B0%E7%BB%84/3794097
隨機存取
https：//baike。baidu。com/item/%E9%9A%8F%E6%9C%BA%E5%AD%98%E5%8F%96
ArrayList原始碼
https：//hg。openjdk。java。net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/ArrayList。java