數(shù)組和鏈表是數(shù)據(jù)結(jié)構(gòu)中最基本的部分，也是其余眾多數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。即使在Java中，這兩種結(jié)構(gòu)使用的也很普遍。這里我們會先對它們進(jìn)行簡要分析。
數(shù)組
在java中，數(shù)組定義為一種基本類型，其可以通過下標(biāo)獲取到對應(yīng)位置的數(shù)據(jù)。那么這種結(jié)構(gòu)的數(shù)據(jù)，在內(nèi)存中是怎么存放的呢？
正如上圖所示，數(shù)組在內(nèi)存中是一段連續(xù)的存儲單元，每個數(shù)據(jù)依次放在每個單元中。分析這種結(jié)構(gòu)，我們可以得出以下幾個結(jié)論：
創(chuàng)建一個數(shù)組，必須聲明其長度，以在內(nèi)存中尋找合適的一段連續(xù)存儲單元。這也意味著數(shù)組的大小是固定的，我們無法動態(tài)調(diào)整其大小。
想要獲取數(shù)組中第i個元素，其時間復(fù)雜度是 O(1)，因為可以根據(jù)其地址直接找到它。同理修改也是。
數(shù)組對查詢表現(xiàn)一般，要想查找一個元素，需要遍歷，時間復(fù)雜度為O(n)。
因為地址連續(xù)，想要在數(shù)組中插入一個元素是復(fù)雜的，因為從插入位置起，后邊的所有元素都需要向后移動一位。同理刪除也是，只是移動方向為向前。并且，當(dāng)數(shù)組存滿時，就無法繼續(xù)插入了。
因為數(shù)組要占據(jù)一整塊內(nèi)存，有可能產(chǎn)生許多的碎片，也可能因為找不到合適的內(nèi)存塊，而導(dǎo)致存儲失敗。
總結(jié)起來就是：數(shù)組大小固定，查找迅速，增刪復(fù)雜，需要完整的內(nèi)存塊，容易產(chǎn)生碎片。
鏈表
鏈表是一種離散存儲結(jié)構(gòu)，其在內(nèi)存中存儲不是連續(xù)的，每個數(shù)據(jù)元素都通過一個指針指向其下一個元素的地址。根據(jù)指針域的不同，鏈表又分為單鏈表、雙向鏈表、循環(huán)鏈表等，這里我們只分析單鏈表。示意圖如下所示：
分析這種結(jié)構(gòu)，我們可以得出以下幾個結(jié)論：
聲明一個鏈表時，不需要知道其長度，也不需要連續(xù)的內(nèi)存塊，所以其大小可以動態(tài)調(diào)整。
鏈表的每個元素都分為數(shù)據(jù)域和指針域，前者是實際存儲的數(shù)據(jù)，后者則指向下一個元素的地址。和數(shù)組相比，每個元素需要占用的內(nèi)存更大了。
要獲取鏈表的第 i 個元素變得復(fù)雜，因為其地址存放在它上一個元素的指針域里，所以只能從第一個元素起，進(jìn)行 i 次操作。同理修改也是。
鏈表對查詢表現(xiàn)也一般，需要遍歷，時間復(fù)雜度為O(n)。
增加與刪除一個元素更方便了，因為沒有對內(nèi)存地址的限制，我們只需要在對應(yīng)節(jié)點合理處理下指針域的值，就可以把一個元素插入鏈表或者從鏈表刪除。
鏈表對內(nèi)存的要求很小，只要能夠存儲下一個數(shù)據(jù)元素的內(nèi)存塊都可以使用，因此不會造成碎片化。
總結(jié)起來就是：大小可以動態(tài)調(diào)整，增刪迅速，查找較慢，數(shù)據(jù)元素所占內(nèi)存略多，不需要整塊內(nèi)存塊，不會造成碎片化。
數(shù)組與鏈表的選擇
通過以上分析，數(shù)組和鏈表對我們影響最大的幾點區(qū)別在于：
- 數(shù)組按位置查找迅速，鏈表增刪方便
- 數(shù)組是固定大小，鏈表可以隨時擴(kuò)充與縮減
- 鏈表每個元素占據(jù)內(nèi)存略多于數(shù)組
- 數(shù)組和鏈表在查詢方面表現(xiàn)都比較一般，耗時較長
在數(shù)據(jù)量很小，內(nèi)容基本固定時，我們選擇何種數(shù)據(jù)結(jié)構(gòu)的影響并不大。但當(dāng)數(shù)據(jù)量較大時，如果我們需要對數(shù)據(jù)進(jìn)行頻繁的插入刪除，我們應(yīng)該選擇鏈表，如果我們需要頻繁的獲取某個位置的元素，我們應(yīng)該選擇數(shù)組。數(shù)組與鏈表并沒有明確的優(yōu)劣之分，根據(jù)不同的使用場景進(jìn)行不同的選擇，才是這兩種結(jié)構(gòu)使用的最佳方式。
上一篇：Java集合源碼分析之開篇
我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~
編程之路，道阻且長。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。
