ArrayList和LinkedList的效率对比

2017-10-03

JAVA

正文

List相信大家都使用得很多，其中ArrayList和LinkedList是使用最多的2个，本文将从源码角度解读2者的异同，效率和使用场景。

正文

存储结构

LinkedList是靠一个名为Node的数据结构来存储数据和前后元素的指针，和双向链表类似。first和last分别存储了第一个和最后一个元素

transient Node<E> first;
transient Node<E> last;
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;
    }
}

其中item存储了实际的元素数据，next是指向了下一个元素，prev指向了前一个元素

而ArrayList直接通过transient Object[] elementData一个Object的数组存储数据

插入

ArrayList在插入之前需要通过ensureCapacityInternal方法先计算下加入一个元素后，elementData数组的大小和当前所需要的大小，若大于于当前数组的大小，则需要进行resize和arrayCopy操作。
1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

resize和arrayCopy主要通过下面的grow方法执行的

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

一般情况下，ArrayList的插入操作是O(1)的时间复杂度，但是当需要resize的时候为O(n)；类似，add(int index, E element)的时间复杂度一般是O(n/2)，需要相应挪动插入的位置之后的元素。

LinkedList的插入操作即在链表后加一个元素，先创建一个Node，当前插入的元素的prev指向last Node，将last赋值为当前插入Node。如果插入前的last不为null，则将last Node的next指向当前插入的元素；反之则将first也赋值为当前插入的Node（即空LinkedList插入元素后，last和first都指向同一个元素）

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

LinkedList的插入操作的时间复杂度是O(1)；相应的add(int index, E element)的一般时间复杂度是O(n/4)，从链表前后同时搜索，如果index=linkedlist.size()/2，那么是最坏情况，为O(n/2)

取元素

ArrayList直接根据数组下标获取相应的元素，所以时间复杂度为O(1)，这也是ArrayList的最大的好处
1
2
3
4
5
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
而LinkedList需要从第一个或最后一个Node往中间遍历，所以其时间复杂度和add(int index, E element)类似，一般时间复杂度是O(n/4)，最坏为O(n/2)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int 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;
    }
}

删除

当删除某个元素时remove(int index)，ArrayList需要进行resize和arrayCopy操作，所以时间复杂度也为O(n/2)。只有当删除的是最后一个元素时，不用进行上述操作。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

LinkedList删除操作和取元素的时间复杂度一样，因为也是要先通过node方法来找到要被删除的元素，再进行改变其前后元素的prev和next指针，所以其时间复杂度是O(n/4)，最坏为O(n/2)
1
2
3
4
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

Iterator

使用Iterator迭代器循环时，可以进行add和remove操作。

        List<String> listA = new ArrayList<>();
//List<String> listB = new LinkedList<>();
        ListIterator<String> iteratorA = listA.listIterator();
        while (iteratorA.hasNext()) {
            String temp = iteratorA.next();
            // iteratorA.add("some string");iteratorA.remove()
        }
        System.out.println(listA.toString());

ArrayList在迭代遍历时，add和remove操作的时间复杂度都为O(n/2)，因为其需要将操作的元素之后的所有元素进行数组移位操作，即resize和arrayCopy
LinkedList在迭代遍历时，add和remove操作的时间复杂度都为O(1)，这也是LinkedList的主要优势

总结

ArrayList的优势在于随机快速读取，其直接在末尾插入元素的效率也很高。唯一需要注意的是，其resize的时候，需要一定的开销。所以如果你提前能预估ArrayList的大小，你可以在实例化时，给他赋一个initialCapacity，可以减小resize的次数。
LinkedList的优势在于利用Iterator迭代器循环时，其插入和删除的效率都是最高的。
在存储空间上，LinkedList相比ArrayList的每个元素都有更多的开销，因为还存储了指向下一个和前一个元素的指针。所以如果你的list很大的话，这一点也需要考虑进去。

上一篇：利用docker-compose快速部署php-fpm+nginx环境

下一篇：API设计和代码结构组织心得