ArrayList LinkedList 源码分析, 性能分析

作者: 昵称全尼马被注册了 | 来源:发表于2017-03-22 20:23 被阅读0次

Java中常用到ArrayList和LinkedList，面试中也常问到两者的区别，各自的使用场景。要想清楚的明白他们的区别，那还是得从源码入手。

List接口

List接口中的方法有很多，但最重要的无非是增删查改，我们从ArrayList与LinkedList的实现上来讨论他们的增删查改性能问题。先列出这几个重要的方法:

public interface List<E> extends Collection<E> {
    ...
    //增
    boolean add(E e); 
    void add(int index, E element);
    //查
    E get(int index);
    //改
    E set(int index, E element);
    //删
    E remove(int index);
    boolean remove(Object o);
    ...
}

ArrayList

构造函数

ArrayList底层使用的是动态数组，我们常用到的构造方法一般是如下两种:

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

从源码可以看出，两者的区别在于初始化数组的长度，前者给定一个空数组，后者若initialCapacity大于0即给定一个initialCapacity大小的数组。
同时，第一段源码的注释还提到了，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA是为了不同的扩展策略。

添加一个元素

    private int size;

    public boolean add(E e) {
        //增加一个元素首先得保证底层数组不越界
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private static final int DEFAULT_CAPACITY = 10;

    private void ensureCapacityInternal(int minCapacity) {
        //之前使用的是ArrayList()作为构造函数的话，第一次扩展把空数组扩展成size=10的数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //这个变量记录了对ArrayList修改的次数(Fail-Fast 就是检测的这个变量)
        modCount++;

        //当前数组已没有更多的容量，则需要动态扩展
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //即newCapacity =1.5倍oldCapacity，所以ArrayList每次动态扩展是1.5倍的扩展 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // ArrayList不适合Add很多的场景，每当底层数组扩容后需要把所有的元素从老数组copy到新数组
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

添加元素时会检测数组大小是否满足条件，不满足会去新建一个更大的数组，把原来数组中的元素都copy过来，可以看出，对于ArrayList的add操作来讲，是比较低效的(当需要扩容时)。
另外还有个public void add(int index, E element)方法，它在指定位置add元素时，需要把指定位置后面的所有元素都往后移动一个位置，所以也是比较低效的。

读取一个元素

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

可以看到，ArrayList的Get是非常高效的，只要index没有越界，直接从底层数组中返回即可，这也是ArrayList的优势所在。

修改一个元素

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

ArrayList的Set也很高效，直接往数组中写即可。

删除一个元素

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            //把index后面的元素整体向前移动，可以看出这步是非常耗资源的
            System.arraycopy(elementData, index+1, elementData, index, numMoved);

        //放弃对最后一个元素的引用，让GC能回收掉它
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArrayList在做删除操作时，因为需要把后面的所有元素整体前移来填空，所也也是非常耗资源的。
另外还有个public boolean remove(Object o)方法，这个是做一次遍历查询，然后删除。

LinkedList

构造函数

通过名字就可知道，LinkedList底层使用的是链表的形式去实现的，它的构造函数什么也没干:

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

添加一个元素

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    transient Node<E> last;    
    transient Node<E> first;

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

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

代码还是很简单的，add一个元素就直接把这个元素放到链表的末端即可。但需要注意的是，相对于ArrayList的add方法，LinkedList的add方法并不见得高效，而且当数据量大后还远慢于ArrayList。
同时，LinkedList还是双向链表，所以内部同时保留了transient Node<E> last和transient Node<E> first;的引用。

读取一个元素

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    Node<E> node(int index) {
        // assert isElementIndex(index);
        // 看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;
        }
    }

读取元素的代码也比较简单，首先check index是否合法，然后遍历链表查找对应元素，查找时用到点小技巧，通过查看index更靠近链表的哪一端，决定从哪一端去遍历。LinkedList在查找时需要遍历，所以相对于ArrayList的随机存取来说，会低效一些。

修改一个元素

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

和查询一样，也使用到了Node<E> node(int index)这个方法去遍历查找，所以也是相对低效的。

删除一个元素

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

首先查找到这个元素（同样使用到了Node<E> node(int index)去查询），然后把它从链表里断出来。因为有遍历查询的存在，所以效率也不会很高。但相对于ArrayList的整块元素的copy来说，效率应该会好一些。

性能实验

顺序添加(`boolean add(E e)`)

从源码中分析可以得出时间复杂度:

LinkedList<E>：O(1)
ArrayList<E>：O(1) amortized, but O(n) worst-case since the array must be resized and copied

咋一看，感觉LinkedList的性能应该优于ArrayList，但实验结做下来却不是这样。这里分别向两个List中添加大量元素:

    public static void main(String[] args) throws CloneNotSupportedException {

        sequenceAdd();
        
    }

    private static void sequenceAdd() {
        
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        
        Long start = System.currentTimeMillis();
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for(int temp : arr){
            arrayList.add(temp);
        }
        System.out.println((System.currentTimeMillis() - start)/1000.0 + "s");
        
        Long start2 = System.currentTimeMillis();
        LinkedList<Integer> LinkedList = new LinkedList<Integer>();
        for(int temp : arr){
            LinkedList.add(temp);
        }
        System.out.println((System.currentTimeMillis() - start2)/1000.0 + "s");
        
    }

ArrayList: 0.631s
LinkedList: 26.14s

通过结果可以看出，LinkedList慢了不止一点。开始怀疑是GC的原因，分别注释重试后发现仍然不是一个量级上的，LinkedList就是慢了许多。
下面是把初始元素个数少去10倍和100倍的情况，从结果可以看出，当数据量少去100倍后两个List的耗时回归同一量级了。

ArrayList: 0.081s
LinkedList: 3.005s

ArrayList: 0.01s
LinkedList: 0.014s

所以对于顺序添加boolean add(E e)来说，ArrayList的效率是优于LinkedList的。造成这种现象的原因我觉得是，LinkedList每次都需要去给Node分配内存所以不见得会快。而ArrayList在经历了一次次扩容后，数据量越大，后面的扩容次数反而降了下来，而且对于数组的复制这种方法，底层应该是做了不少优化。

随机添加(`void add(int index, E element)`)

从源码中分析可以得出时间复杂度:

LinkedList<E>：O(n/4) average
ArrayList<E>：O(n/2) average

    private static void randomAdd() {
        
        //准备数据
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for(int temp : arr){
            arrayList.add(temp);
        }
        LinkedList<Integer> LinkedList = new LinkedList<Integer>();
        for(int temp : arr){
            LinkedList.add(temp);
        }
        
        Random random =new Random();
        //ArrayList随机add
        Long start = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            arrayList.add(random.nextInt(999999), 999);
        }
        System.out.println("ArrayList: " + (System.currentTimeMillis() - start)/1000.0 + "s");
        
        //LinkedList随机add
        Long start2 = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            LinkedList.add(random.nextInt(999999), 999);
        }
        System.out.println("LinkedList: " + (System.currentTimeMillis() - start2)/1000.0 + "s");
        
    }

ArrayList: 5.359s
LinkedList: 0.144s

从结果中可以看出，对于随机插入void add(int index, E element)，LinkedList的效率是优于ArrayList的。对于这个结果还是好理解，LinkedList只需要遍历到index的位置，在链表中插入一个Node即可，而ArrayList需要移动整块的元素。
但把数据量减少100倍后，两者的效率也差不多了。

随机访问(`E get(int index)`)

从源码中分析可以得出时间复杂度:

LinkedList<E>：O(n/4) average
ArrayList<E>：O(1) <--- main benefit of ArrayList<E>

    private static void get() {
        
        //准备数据
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for(int temp : arr){
            arrayList.add(temp);
        }
        LinkedList<Integer> LinkedList = new LinkedList<Integer>();
        for(int temp : arr){
            LinkedList.add(temp);
        }
        
        Random random =new Random();
        //ArrayList随机get
        Long start = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            arrayList.get(random.nextInt(999999));
        }
        System.out.println("ArrayList: " + (System.currentTimeMillis() - start)/1000.0 + "s");
        
        //LinkedList随机get
        Long start2 = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            LinkedList.get(random.nextInt(999999));
        }
        System.out.println("LinkedList: " + (System.currentTimeMillis() - start2)/1000.0 + "s");
        
    }

ArrayList: 0.0s
LinkedList: 0.133s

可以看到ArrayList的随机访问完胜。而LinkedList由于需要遍历，所以会慢一些，O(n/4) 的平均时间复杂度是因为LinkedList会检查index离哪端近，从近的那端去遍历。

随机修改(`E set(int index, E element)`)

原理和上面的随机访问一致，所以性能也和上面一致。

随机删除(`E remove(int index)`)

从源码中分析可以得出时间复杂度:

LinkedList<E>：O(n/4) average
ArrayList<E>：O(n/2) average

    private static void remove() {
        
        //准备数据
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for(int temp : arr){
            arrayList.add(temp);
        }
        LinkedList<Integer> LinkedList = new LinkedList<Integer>();
        for(int temp : arr){
            LinkedList.add(temp);
        }
        
        Random random =new Random();
        //ArrayList随机get
        Long start = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            arrayList.remove(random.nextInt(999999));
        }
        System.out.println("ArrayList: " + (System.currentTimeMillis() - start)/1000.0 + "s");
        
        //LinkedList随机get
        Long start2 = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            LinkedList.remove(random.nextInt(999999));
        }
        System.out.println("LinkedList: " + (System.currentTimeMillis() - start2)/1000.0 + "s");
        
    }

ArrayList: 4.455s
LinkedList: 0.11s

原理和随机添加一样，ArrayList在删除中间元素后需要整块移动，LinkedList查询到index后直接删除Node;

删除指定对象(`boolean remove(Object o)`)

    private static void removeSpecific() {
        
        //准备数据
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for(int temp : arr){
            arrayList.add(temp);
        }
        LinkedList<Integer> LinkedList = new LinkedList<Integer>();
        for(int temp : arr){
            LinkedList.add(temp);
        }
        
        //ArrayList随机get
        Long start = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            arrayList.remove(new Integer((int) (Math.random() * 100)));
        }
        System.out.println("ArrayList: " + (System.currentTimeMillis() - start)/1000.0 + "s");
        
        //LinkedList随机get
        Long start2 = System.currentTimeMillis();
        for(int i=0; i<100; i++){
            LinkedList.remove(new Integer((int) (Math.random() * 100)));
        }
        System.out.println("LinkedList: " + (System.currentTimeMillis() - start2)/1000.0 + "s");
        
    }

ArrayList: 4.341s
LinkedList: 0.0s

在删除指定对象时，ArrayList与LinkedList都需要去遍历查找，不同的是ArrayList在删除后需要整块移动元素，所以更慢。

总结

ArrayList因为是基于动态数组去实现，在随机存取时，有着良好的性能。而增删时需要扩容，整块移动元素，所以相对较慢。但在数据量很大，顺序添加时是个例外，这种情况下它的性能优于LinkedList。
LinkedList因为是基于链表实现，随机增删较快，而存取时需要遍历查询，相对于ArrayList会更慢。
之后会比较下两种实现的迭代器性能。

对于一开始提到的几种方法，做个总结图表:

	`add(e)`	`add(index, e)`	`get(index)`	`set(index, element)`	`remove(index)`	`remove(obj)`
LinkedList		√			√	√
ArrayList	√		√	√

add(e) 顺序添加
add(index, e) 随机添加
get(index) 随机取
set(index, element) 随机存
remove(index) 随机删除
remove(obj) 删除指定对象

代码

Code

参考

When to use LinkedList over ArrayList?

ArrayList LinkedList 源码分析, 性能分析

List接口

ArrayList

构造函数

添加一个元素

读取一个元素

修改一个元素

删除一个元素

LinkedList

构造函数

添加一个元素

读取一个元素

修改一个元素

删除一个元素

性能实验

顺序添加(`boolean add(E e)`)

随机添加(`void add(int index, E element)`)

随机访问(`E get(int index)`)

随机修改(`E set(int index, E element)`)

随机删除(`E remove(int index)`)

删除指定对象(`boolean remove(Object o)`)

总结

代码

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

技术干货

数据结构和算法分析

程序员

ArrayList LinkedList 源码分析, 性能分析

List接口

ArrayList

构造函数

添加一个元素

读取一个元素

修改一个元素

删除一个元素

LinkedList

构造函数

添加一个元素

读取一个元素

修改一个元素

删除一个元素

性能实验

顺序添加(boolean add(E e))

随机添加(void add(int index, E element))

随机访问(E get(int index))

随机修改(E set(int index, E element))

随机删除(E remove(int index))

删除指定对象(boolean remove(Object o))

总结

代码

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

技术干货

数据结构和算法分析

程序员

顺序添加(`boolean add(E e)`)

随机添加(`void add(int index, E element)`)

随机访问(`E get(int index)`)

随机修改(`E set(int index, E element)`)

随机删除(`E remove(int index)`)

删除指定对象(`boolean remove(Object o)`)