前言

今天介紹一下Java的兩個(gè)集合類，ArrayList和LinkedList，這兩個(gè)集合的知識(shí)點(diǎn)幾乎可以說(shuō)面試必問(wèn)的。

對(duì)于這兩個(gè)集合類，相信大家都不陌生，ArrayList可以說(shuō)是日常開(kāi)發(fā)中用的最多的工具類了，也是面試中幾乎必問(wèn)的，LinkedList可能用的少點(diǎn)，但大多數(shù)的面試也會(huì)有所涉及，尤其是關(guān)于這兩者的比較可以說(shuō)是家常便飯，所以，無(wú)論從使用上還是在面試的準(zhǔn)備上，對(duì)于這兩個(gè)類的知識(shí)點(diǎn)我們都要有足夠的了解。

ArrayList

ArrayList是List接口的一個(gè)實(shí)現(xiàn)類，底層是基于數(shù)組實(shí)現(xiàn)的存儲(chǔ)結(jié)構(gòu)，可以用于裝載數(shù)據(jù)，數(shù)據(jù)都是存放到一個(gè)數(shù)組變量中，

transient Object[] elementData;

transient是一個(gè)關(guān)鍵字，它的作用可以總結(jié)為一句話：將不需要序列化的屬性前添加關(guān)鍵字transient，序列化對(duì)象的時(shí)候，這個(gè)屬性就不會(huì)被序列化。 你可能會(huì)覺(jué)得奇怪，ArrayList可以被序列化的啊，源碼可是實(shí)現(xiàn)了java.io.Serializable接口啊，為什么數(shù)組變量還要用transient定義呢？

別急，關(guān)于這個(gè)問(wèn)題，我們后面會(huì)討論到，不賣個(gè)關(guān)子，你們?cè)趺磿?huì)看到最后，然后給我點(diǎn)在看呢？

當(dāng)我們新建一個(gè)實(shí)例時(shí)，ArrayList會(huì)默認(rèn)幫我們初始化數(shù)組的大小為10


/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

但請(qǐng)注意，這個(gè)只是數(shù)組的容量大小，并不是List真正的大小，List的大小應(yīng)該由存儲(chǔ)數(shù)據(jù)的數(shù)量決定，在源碼中，獲取真實(shí)的容量其實(shí)是用一個(gè)變量size來(lái)表示，

private int size;

在源碼中，數(shù)據(jù)默認(rèn)是從數(shù)組的第一個(gè)索引開(kāi)始存儲(chǔ)的，當(dāng)我們添加數(shù)據(jù)時(shí)，ArrayList會(huì)把數(shù)據(jù)填充到上一個(gè)索引的后面去，所以，ArrayList的數(shù)據(jù)都是有序排列的。而且，由于ArrayList本身是基于數(shù)組存儲(chǔ)，所以查詢的時(shí)候只需要根據(jù)索引下標(biāo)就可以找到對(duì)于的元素，查詢性能非常的高，這也是我們非常青睞ArrayList的最重要的原因。

但是，數(shù)組的容量是確定的啊，如果要存儲(chǔ)的數(shù)據(jù)大小超過(guò)了數(shù)組大小，那不就有數(shù)組越界的問(wèn)題？

關(guān)于這點(diǎn)，我們不用擔(dān)心，ArrayList幫我們做了動(dòng)態(tài)擴(kuò)容的處理，如果發(fā)現(xiàn)新增數(shù)據(jù)后，List的大小已經(jīng)超過(guò)數(shù)組的容量的話，就會(huì)新增一個(gè)為原來(lái)1.5倍容量的新數(shù)組，然后把原數(shù)組的數(shù)據(jù)原封不動(dòng)的復(fù)制到新數(shù)組中，再把新數(shù)組賦值給原來(lái)的數(shù)組對(duì)象就完成了。

擴(kuò)容之后，數(shù)組的容量足夠了，就可以正常新增數(shù)據(jù)了。

除此之外，ArrayList提供支持指定index新增的方法，就是可以把數(shù)據(jù)插入到設(shè)定的索引下標(biāo)，比如說(shuō)我想把元素4插入到3后面的位置，也就是現(xiàn)在5所在的地方，

插入數(shù)據(jù)的時(shí)候，ArrayList的操作是先把3后面的數(shù)組全部復(fù)制一遍，然后將這部分?jǐn)?shù)據(jù)往后移動(dòng)一位，其實(shí)就是逐個(gè)賦值給后移一位的索引位置，然后3后面就可以空出一個(gè)位置，把4放入就完成了插入數(shù)據(jù)的操作了

刪除的時(shí)候也是一樣，指定index，然后把后面的數(shù)據(jù)拷貝一份，并且向前移動(dòng)，這樣原來(lái)index位置的數(shù)據(jù)就刪除了。

到這里我們也不難發(fā)現(xiàn)，這種基于數(shù)組的查詢雖然高效，但增刪數(shù)據(jù)的時(shí)候卻很耗性能，因?yàn)槊吭鰟h一個(gè)元素就要移動(dòng)對(duì)應(yīng)index后面的所有元素，數(shù)據(jù)量少點(diǎn)還無(wú)所謂，但如果存儲(chǔ)上千上萬(wàn)的數(shù)據(jù)就很吃力了，所以，如果是頻繁增刪的情況，不建議用ArrayList。

既然ArrayList不建議用的話，這種情況下有沒(méi)有其他的集合可用呢？

當(dāng)然有啊，像我這樣的暖男肯定是第一時(shí)間告訴你們的，這就引出了我們下面要說(shuō)的LinkedList。

LinkedList

LinkedList 是基于雙向鏈表實(shí)現(xiàn)的，不需要指定初始容量，鏈表中任何一個(gè)存儲(chǔ)單元都可以通過(guò)向前或者向后的指針獲取到前面或者后面的存儲(chǔ)單元。在 LinkedList 的源碼中，其存儲(chǔ)單元用一個(gè)Node類表示：

private static class Node<E> {
 E item;
 Node<E> next; 
 Node<E> prev;

 Node(Node<E> prev, E element, Node<E> next) {
 this.item = element;
 this.next = next;
 this.prev = prev;
 }
}

Node中包含了三個(gè)成員，分別是存儲(chǔ)數(shù)據(jù)的item，指向前一個(gè)存儲(chǔ)單元的點(diǎn)prev和指向后一個(gè)存儲(chǔ)單元的節(jié)點(diǎn)next ，通過(guò)這兩個(gè)節(jié)點(diǎn)就可以關(guān)聯(lián)前后的節(jié)點(diǎn)，組裝成為鏈表的結(jié)構(gòu)，

因?yàn)橛斜４媲昂蠊?jié)點(diǎn)的地址，LinkedList增刪數(shù)據(jù)的時(shí)候不需要像ArrayList那樣移動(dòng)整片的數(shù)據(jù)，只需要通過(guò)引用指定index位置前后的兩個(gè)節(jié)點(diǎn)即可，比如我們要在李白和韓信之間插入孫悟空的節(jié)點(diǎn)，只需要像這樣處理下節(jié)點(diǎn)之間的指向地址：

刪除數(shù)據(jù)也是同樣原理，只需要改變index位置前后兩個(gè)節(jié)點(diǎn)的指向地址即可。

這樣的鏈表結(jié)構(gòu)使得LinkedList能非常高效的增刪數(shù)據(jù)，在頻繁增刪的情景下能很好的使用，但不足之處也是有的。

雖然增刪數(shù)據(jù)很快，但查詢就不怎么樣了，LinkedList是基于雙向鏈表存儲(chǔ)的，當(dāng)查詢對(duì)應(yīng)index位置的數(shù)據(jù)時(shí)，會(huì)先計(jì)算鏈表總長(zhǎng)度一半的值，判讀index是在這個(gè)值的左邊還是右邊，然后決定從頭結(jié)點(diǎn)還是從尾結(jié)點(diǎn)開(kāi)始遍歷，

Node<E> node(int index) {
 // assert isElementIndex(index);

 if (index < (size >> 1)) {
  Node<E> x = first;
  for (int i = 0; i < index; i++)
  x = x.next;
  return x;
 } else {
  Node<E> x = last;
  for (int i = size - 1; i > index; i--)
  x = x.prev;
  return x;
 }
 }

雖然已經(jīng)二分法來(lái)做優(yōu)化，但依然會(huì)有遍歷一半鏈表長(zhǎng)度的情況，如果是數(shù)據(jù)量非常多的話，這樣的查詢無(wú)疑是非常慢的。

這也是LinkedList最無(wú)奈的地方，魚(yú)和熊掌不可兼得，我們既想查的快，又想增刪快，這樣的好事怎么可能都讓我們遇到呢？所以，一般建議LinkedList使用于增刪多，查詢少的情景。

除此之外，LinkedList對(duì)內(nèi)存的占用也是比較大的，畢竟每個(gè)Node都維護(hù)著前后指向地址的節(jié)點(diǎn)，數(shù)據(jù)量大的話會(huì)占用不少內(nèi)存空間。

兩者哪個(gè)更占空間？

講到這，你是不是對(duì)標(biāo)題的那個(gè)問(wèn)題成竹在胸了？

下次有面試官問(wèn)你，ArrayList和LinkedList哪個(gè)更占空間時(shí)，你就可以信誓旦旦的說(shuō)，LinkedList更占空間，我看了薛大佬的文章，肯定不會(huì)錯(cuò)。說(shuō)完你就可以安心坐著，等待面試官露出滿意的笑容，告訴你通過(guò)面試的消息，成功拿下offer指日可待。

如果你真的這么答的話，我也相信面試官一定會(huì)被你的回答所征服，他聽(tīng)完一定會(huì)點(diǎn)點(diǎn)頭，嘴角開(kāi)始上揚(yáng)，然后笑容滿面的告訴你，

感謝你今天過(guò)來(lái)面試，你可以回去等通知了。。。。

哈哈，開(kāi)個(gè)玩笑，不湊多點(diǎn)字可不是我的風(fēng)格。

言歸正傳，表面上看，LinkedList的Node存儲(chǔ)結(jié)構(gòu)似乎更占空間，但別忘了前面介紹ArrayList擴(kuò)容的時(shí)候，它會(huì)默認(rèn)把數(shù)組的容量擴(kuò)大到原來(lái)的1.5倍的，如果你只添加一個(gè)元素的話，那么會(huì)有將近原來(lái)一半大小的數(shù)組空間被浪費(fèi)了，如果原先數(shù)組很大的話，那么這部分空間的浪費(fèi)也是不少的，

所以，如果數(shù)據(jù)量很大又在實(shí)時(shí)添加數(shù)據(jù)的情況下，ArrayList占用的空間不一定會(huì)比LinkedList空間小，這樣的回答就顯得謹(jǐn)慎些了，聽(tīng)上去也更加讓人容易認(rèn)同，但你以為這樣回答就完美了嗎？非也

還記得我前面說(shuō)的那個(gè)transient變量嗎？它的作用已經(jīng)說(shuō)了，不想序列化的對(duì)象就可以用它來(lái)修飾，用transient修飾elementData意味著我不希望elementData數(shù)組被序列化。為什么要這么做呢？

這是因?yàn)樾蛄谢疉rrayList的時(shí)候，ArrayList里面的elementData，也就是數(shù)組未必是滿的，比方說(shuō)elementData有10的大小，但是我只用了其中的3個(gè)，那么是否有必要序列化整個(gè)elementData呢？ 顯然沒(méi)有這個(gè)必要，因此ArrayList中重寫(xiě)了writeObject方法：

private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException{
 // Write out element count, and any hidden stuff
 int expectedModCount = modCount;
 s.defaultWriteObject();

 // Write out size as capacity for behavioural compatibility with clone()
 s.writeInt(size);

 // Write out all elements in the proper order.
 for (int i=0; i<size; i++) {
 s.writeObject(elementData[i]);
 }

 if (modCount != expectedModCount) {
 throw new ConcurrentModificationException();
 }
}

每次序列化的時(shí)候調(diào)用這個(gè)方法，先調(diào)用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData這個(gè)數(shù)組對(duì)象不去序列化它，而是遍歷elementData，只序列化數(shù)組里面有數(shù)據(jù)的元素，這樣一來(lái)，就可以加快序列化的速度，還能夠減少空間的開(kāi)銷。

加上這個(gè)知識(shí)點(diǎn)后，我們對(duì)上面那個(gè)問(wèn)題就可以有更加全面的回答了，如果你下次也遇到這個(gè)問(wèn)題的話，你可以參考一下我的說(shuō)法：

一般情況下，LinkedList的占用空間更大，因?yàn)槊總€(gè)節(jié)點(diǎn)要維護(hù)指向前后地址的兩個(gè)節(jié)點(diǎn)，但也不是絕對(duì)，如果剛好數(shù)據(jù)量超過(guò)ArrayList默認(rèn)的臨時(shí)值時(shí)，ArrayList占用的空間也是不小的，因?yàn)閿U(kuò)容的原因會(huì)浪費(fèi)將近原來(lái)數(shù)組一半的容量，不過(guò)，因?yàn)锳rrayList的數(shù)組變量是用transient關(guān)鍵字修飾的，如果集合本身需要做序列化操作的話，ArrayList這部分多余的空間不會(huì)被序列化。

怎么樣，這樣的回答是不是更加的說(shuō)服力，不僅更加全面，還可能會(huì)給面試官留下好印象，讓他覺(jué)得你是個(gè)有自己思考的求職者，說(shuō)不定當(dāng)場(chǎng)就讓你面試通過(guò)了呢。

總結(jié)

最新評(píng)論