分析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高。