【153期】面試官：談?wù)劤Ｓ玫腁rraylist和Linkedlist的區(qū)別

程序員的成長之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享 

閱讀本文大概需要 2 分鐘。

來自：blog.csdn.net/weixin_42468526/article/details/81178698

Arraylist：底層是基于動態(tài)數(shù)組，根據(jù)下表隨機(jī)訪問數(shù)組元素的效率高，向數(shù)組尾部添加元素的效率高；但是，刪除數(shù)組中的數(shù)據(jù)以及向數(shù)組中間添加數(shù)據(jù)效率低，因為需要移動數(shù)組。

例如最壞的情況是刪除第一個數(shù)組元素，則需要將第2至第n個數(shù)組元素各向前移動一位。而之所以稱為動態(tài)數(shù)組，是因為Arraylist在數(shù)組元素超過其容量大，Arraylist可以進(jìn)行擴(kuò)容（針對JDK1.8  數(shù)組擴(kuò)容后的容量是擴(kuò)容前的1.5倍），Arraylist源碼中最大的數(shù)組容量是Integer.MAX_VALUE-8。

對于空出的8位，目前解釋是 ：①存儲Headerwords；②避免一些機(jī)器內(nèi)存溢出，減少出錯幾率，所以少分配③最大還是能支持到Integer.MAX_VALUE（當(dāng)Integer.MAX_VALUE-8依舊無法滿足需求時）。

以下是Arraylist部分源碼：

Arraylist擴(kuò)容：

Arraylist添加數(shù)據(jù)：（向數(shù)組尾部添加）

向數(shù)組的指定位置添加數(shù)組：

可以看到，只要ArrayList的當(dāng)前容足夠大，add()操作向數(shù)組的尾部的效率非常高的，當(dāng)向數(shù)組指定位置添加數(shù)據(jù)時，會進(jìn)行大量的數(shù)組移動復(fù)制操作。而數(shù)組復(fù)制時，最終將調(diào)用System.arraycopy()方法，因此add()操作的效率還是相當(dāng)高的。

盡管這樣當(dāng)向指定位置添加數(shù)據(jù)時也還是比Linkedlist慢，后者添加數(shù)據(jù)只需要改變指針指向即可。Arraylist刪除數(shù)組也需要移動數(shù)組，效率較慢。

Linkedlist基于鏈表的動態(tài)數(shù)組，數(shù)據(jù)添加刪除效率高，只需要改變指針指向即可，但是訪問數(shù)據(jù)的平均效率低，需要對鏈表進(jìn)行遍歷。

Arraylist get數(shù)據(jù)的源碼：（根據(jù)下標(biāo)訪問，效率高）

Linkedlist訪問數(shù)據(jù)的源碼：（node()函數(shù)遍歷鏈表）

總結(jié)：

1、對于隨機(jī)訪問get和set，ArrayList優(yōu)于LinkedList，因為LinkedList要移動指針。對于新增和刪除操作add和remove，LinedList比較占優(yōu)勢，因為ArrayList要移動數(shù)據(jù)。

2、各自效率問題：

<END>

推薦閱讀：

【152期】面試官：你能說出MySQL主從復(fù)制的幾種復(fù)制方式嗎？

【151期】談?wù)?ZooKeeper 的定位：能解決什么問題？不能解決什么問題？

【150期】面試官：Redis的各項功能解決了哪些問題？

5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機(jī)，樹莓派，等等。在公眾號內(nèi)回復(fù)「2048」，即可免費(fèi)獲?。。?/span>

微信掃描二維碼，關(guān)注我的公眾號

朕已閱