Java面試中關(guān)于容器類List，Set是必問題目。但在我的面試經(jīng)歷中很難遇到滿意的答復(fù)。大部分只能了解其大概使用方法，對其內(nèi)部結(jié)構(gòu)缺乏了解，錯誤的使用方式會導(dǎo)致性能大幅下降。
首先介紹ArrayList，顧名思義內(nèi)部數(shù)據(jù)結(jié)構(gòu)是數(shù)組
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity){
}
在增加元素時(shí)，若容量不足進(jìn)行擴(kuò)充
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
新數(shù)組大小為之前數(shù)組大小*1.5+1 ，加上1保證oldCapacity為1的情況也能擴(kuò)充為2
（類似分頁時(shí)總頁數(shù)=(總記錄數(shù)+ （每頁記錄數(shù)-1）)/每頁記錄數(shù)算法)
刪除元素時(shí)通過 System.arraycopy把刪除位置后的所有元素前移一個位置實(shí)現(xiàn)
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
LinkedList大家都知道是通過鏈表實(shí)現(xiàn)，內(nèi)部是一個雙向鏈表
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
}
插入和刪除都只要改動前后節(jié)點(diǎn)的next和previous實(shí)現(xiàn)
總結(jié)特點(diǎn)如下：
| 類型 | 內(nèi)部結(jié)構(gòu) | 順序遍歷速度 | 隨機(jī)遍歷速度 | 追加代價(jià) | 插入代價(jià) | 刪除代價(jià) | 占用內(nèi)存 |
| ArrayList | 數(shù)組 | 高 | 高 | 中 | 高 | 高 | 低 |
| LinkedList | 雙向鏈表 | 高 | 低 | 低 | 低 | 低 | 中 |
所以：
- 一般順序遍歷情況下使用ArrayList，但注意構(gòu)造函數(shù)中設(shè)置初始大小
- 盡量不對ArrayList進(jìn)行插入或刪除操作(刪除尾部除外),若有多次刪除/插入操作又有隨機(jī)遍歷的需求，可以再構(gòu)建一個ArrayList，把復(fù)合條件的對象放入新ArrayList，而不要頻繁操作原ArrayList
- 經(jīng)常有刪除/插入操作而順序遍歷列表的情況下最適合使用LinkedList
已有 0 人發(fā)表留言，猛擊->>這里<<-參與討論
ITeye推薦