數(shù)組和鏈表是數(shù)據(jù)結(jié)構(gòu)中最基本的部分，也是其余眾多數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)益楼。即使在Java中猾漫，這兩種結(jié)構(gòu)使用的也很普遍。這里我們會先對它們進行簡要分析感凤。
數(shù)組
在java中悯周，數(shù)組定義為一種基本類型，其可以通過下標獲取到對應(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ù)雜的腥刹，因為從插入位置起，后邊的所有元素都需要向后移動一位汉买。同理刪除也是衔峰，只是移動方向為向前。并且，當數(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ù)雜，因為其地址存放在它上一個元素的指針域里尊勿，所以只能從第一個元素起归苍，進行 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ù)組是固定大小仔雷，鏈表可以隨時擴充與縮減
- 鏈表每個元素占據(jù)內(nèi)存略多于數(shù)組
- 數(shù)組和鏈表在查詢方面表現(xiàn)都比較一般蹂析，耗時較長
在數(shù)據(jù)量很小，內(nèi)容基本固定時碟婆，我們選擇何種數(shù)據(jù)結(jié)構(gòu)的影響并不大电抚。但當數(shù)據(jù)量較大時，如果我們需要對數(shù)據(jù)進行頻繁的插入刪除竖共，我們應(yīng)該選擇鏈表喻频，如果我們需要頻繁的獲取某個位置的元素，我們應(yīng)該選擇數(shù)組肘迎。數(shù)組與鏈表并沒有明確的優(yōu)劣之分，根據(jù)不同的使用場景進行不同的選擇锻煌，才是這兩種結(jié)構(gòu)使用的最佳方式妓布。
上一篇：Java集合源碼分析之開篇
我是飛機醬，如果您喜歡我的文章宋梧，可以關(guān)注我~
編程之路匣沼，道阻且長。唯捂龄，路漫漫其修遠兮释涛，吾將上下而求索。
