ArrayList LinkedList 源码分析, 性能分析

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?

最后编辑于：2017.12.06 05:06:30

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,311评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,339评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,671评论 0赞 342
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,252评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,253评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,031评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,340评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,973评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,466评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,937评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,039评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,701评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,254评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,259评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,485评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,497评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,786评论 2赞 345

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)`)