分析ArrayList和LinkedList的差別

我們總說數組随機通路時性能更優，連結清單在進行增删操作時性能更優。姑且試着從JDK源碼的ArrayList和LinkedList一看究竟吧。

以增加和删除元素分析ArrayList和LinkedList

add操作:

public boolean add(E e) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}
           

add()方法的性能取決于ensureCapacity()

ArrayList的目前容量足夠大時，add()操作的效率很高。

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);
}
}
           

但是當ArrayList的需求大于目前數組容量，需要進行擴容。

擴容過程會進行數組複制。

LinkedList：

add()操作：

public boolean add(E e) {
addBefore(e, header);
    return true;
}
           

LinkedList為雙端循環連結清單，在header之前添加元素就是在末尾添加元素

LinkedList是連結清單結構，不需要維護容量大小。

但是每次元素增加都要new一個Entry對象并進行系列指派操作。可能對性能

有影響。

add增加元素到集合任意位置：

public void add(int index, E element) {
if (index > size || index < 0)
    throw new IndexOutOfBoundsException(
    "Index: "+index+", Size: "+size);

ensureCapacity(size+1);  // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
         size - index);
elementData[index] = element;
size++;
}
           

ArrayList基于數組實作，存在于連續的記憶體空間。在任意位置進行插入元素，

那麼該位置之後的元素将重新排列。除此以外iain，每次還會進行一次數組複制

，效率較低。

remove()操作:

ArrayList中remove()和add()雷同

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類中：

public E remove(int index) {
    return remove(entry(index));
}

/**
 * Returns the indexed entry.
 */
private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}
           

`

LinkedList的實作中，首先要通過循環找到要删除的元素。如果要删除的位置

處于List的前半段，則從前往後找；若其位置處于後半段，則從後往前找。

是以無論要删除較為靠前或者靠後的元素都是非常高效的。但要移除List中間的

元素卻幾乎要周遊半個List，在List擁有大量元素的情況下，效率很低。

容量參數：

容量參數是ArrayList和Vector等基于數組的List的特有性能參數。表示初始化

數組大小。

合理的數組大小有助于減少數組擴容，提高系統性能。

合理數組大小能夠有效減少系統消耗時間

周遊:

JDK1.5之後，有3中周遊方式：

forEach,疊代器Iterator，for循環.。

不過面向接口List，經常使用疊代器方法周遊。

ArrayList不僅隻适用于随機查詢，其實也可以進行增删操作。

而且，越靠近尾部的元素進行增删時，其實效率比LinkedList高。