源码上分析ArrayList/LinkedList的性能

我不是女神ヾ 2022-05-25 03:47 188阅读 0赞

环境：

JDK8

概述：

ArrayList底层是一个数组，数组有容量限制，超出限制时会增加50%容量，默认第一次插入元素时创建大小为10的数组。

LinkedList底层维护一个Node的双向链表

![69479669.jpg][]

参考其内部类Node<E>

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之前判断数组容量，当数组容量不足时，会进行扩容

public boolean add(E e) {
       
        // 确定ArrayList的容量大小 必要时进行扩容
        // 注意：size + 1，保证资源空间不被浪费，
        //按当前情况，保证要存多少个元素，就只分配多少空间资源
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    /**
    * 私有方法：明确 ArrayList 的容量，提供给本类使用的方法
     * - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效
     * @param minCapacity    指定的最小容量
     */
    private void ensureCapacityInternal(int minCapacity) {
       
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
       
        // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的
        modCount++;
    
        // 防止溢出代码：确保指定的最小容量 > 数组缓冲区当前的长度
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /**
    * 私有方法：扩容，以确保 ArrayList 至少能存储 minCapacity 个元素
     * - 扩容计算：newCapacity = oldCapacity + (oldCapacity >> 1);  扩充当前容量的1.5倍
     * @param minCapacity    指定的最小容量
     */
    private void grow(int minCapacity) {
       
        // overflow-conscious code
        //防止溢出代码
        int oldCapacity = elementData.length;
        // 运算符 >> 是带符号右移. 如 oldCapacity = 10,则 newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) // 若 newCapacity 大于最大存储容量，则进行大容量分配
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList 核心是在新建Node后会修改相邻Node的next及prev

public void add(E e) {
       
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
    
    /**
    * 将其作为尾节点
     * Links e as last element.
     */
    void linkLast(E e) {
       
        //将新加节点的前驱指向last节点
        final java.util.LinkedList.Node<E> l = last;
        //创建节点(前驱是last节点，元素为e，后继为null节点)
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null);
        //将last节点修改为指向新节点
        last = newNode;
        //判断新节点的前节点(就是以前的last节点)是不是为空
        if (l == null)
            //如果新节点的前节点为空，
            // 说明这个list集合是一个空集合，这个新加节点是添加的第一个节点，
            //将first节点修改为指向新节点
            first = newNode;
        else
            //如果新节点的前节点不为空
            //说明这个list集合有元素
            //将前节点的后继修改为新节点
            l.next = newNode;
        size++;
        modCount++;
    }
    
    /**
    * //在指定节点前插入节点，节点succ不能为空
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, java.util.LinkedList.Node<E> succ) {
       
        // assert succ != null;
        final java.util.LinkedList.Node<E> pred = succ.prev;//取出指定节点的前驱节点
        //新建一个以指定节点为后继节点，指定节点的前驱节点为前驱节点的节点
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
        //修改指定节点的前驱为新节点
        succ.prev = newNode;
        if (pred == null)
            //如果指定节点为first节点
            first = newNode;
        else
            //将指定节点的后节点指向新节点
            pred.next = newNode;
        size++;
        modCount++;
    }

性能比较：

ArrayList如果不考虑扩容的情况，效率和LinkedList不会有太大差别，当然一旦数组容量不足须要扩容时，ArrayList会将old array copy至扩容后的new array，ArrayList的初始数组大小为10，所以在大批量的add操作中，性能会比LinkedList差。

Add 向指定位置添加元素

ArrayList 通过arraycopy方法实现指定位置之后的元素向后顺移一位

public void add(int index, E element) {
       
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }

LinkedList 和末位追加没太大区别，同样是修改相邻Node的next及prev

public void add(int index, E element) {
       
        checkPositionIndex(index);
    
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    /**
    * Returns the (non-null) Node at the specified element index.
     */
    java.util.LinkedList.Node<E> node(int index) {
       
        // assert isElementIndex(index);
    
        // 判断位置在链表前半段或者是后半段
        if (index < (size >> 1)) {
       
            java.util.LinkedList.Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
       
            java.util.LinkedList.Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

性能比较：

一目了然，ArrayList每次添加元素后，须要对后面的元素依次顺移一位，效率上和LinkedList没法比

get元素

ArrayList直接按数组下标访问元素，性能上没有多余损耗

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

LinkedList 须要遍历链表中的元素

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

性能比较：由于ArrayList直接按数组下标访问元素，性能上没有多余损耗，在get元素上的效率比LinkedList高

remove元素

和Add一样，ArrayList在remove（末位移除除外）之后须要对后面的元素下标进行变更

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的next及prev

public E remove(int index) {
       
        checkElementIndex(index);
        return unlink(node(index));
    }
    
    E unlink(java.util.LinkedList.Node<E> x) {
       
        // assert x != null;
        final E element = x.item;
        final java.util.LinkedList.Node<E> next = x.next;
        final java.util.LinkedList.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;
    }

性能比较：

同向指定位置添加元素一样，ArrayList还要copy一份新的数组，性能上和LinkedList没法比

总结：

ArrayList内部维护一个数组，末位追加元素和get元素的性能很客观，但是在指定位置上进行添加移除操作上的性能较LinkedList差。

LinkedList是一个双向链表，不管是添加抑或是移除，额外操作只是修改相邻元素，性能强大，但是get元素须要遍历获取，性能上较ArrayList差。

ArrayList强在读数据，LinkedList强在写数据，如果集合仅需要读取或者不涉及大批量元素的添加，以及不涉及大批量对中间元素的添加移除操作，建议使用ArrayList，其余情况建议使用LinkedList。

[69479669.jpg]: http://opflvhdw3.bkt.clouddn.com/17-12-29/69479669.jpg