LinkedList与ArrayList新增/删除元素效率哪个更快

ArrayList 与 LinkedList 删除元素比较

删除元素和新增元素的原理是一样的，所以删除元素的操作和新增元素的操作耗时也是很相近

这里就不再赘述

ArrayList 与 LinkedList 遍历元素比较

测试结果非常明显，对于 LinkedList 来说，如果使用 for 循环的话，效率特别低，但是 ArrayList 使用 for 循环去遍历的话，就比较高

为啥呢？

emmm ，得从源码说起

先来看 ArrayList 的源码吧，这个比较简单

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

能够看到， ArrayList 实现了 List ， RandomAccess ， Cloneable 还有 Serializable 接口

你是不是对 RandomAccess 这个接口挺陌生的？这是个啥？

但是通过查阅源码能够发现它也只是个空的接口罢了，那 ArrayList 为啥还要去实现它嘞

因为 RandomAccess 接口是一个标志接口，它标识着“只要实现该接口的 list 类，都可以实现快速随机访问”

实现快速随机访问？你能想到什么？这不就是数组的特性嘛！可以直接通过 index 来快速定位 & 读取

那你是不是就能想到， ArrayList 是数组实现的，所以实现了 RandomAccess 接口， LinkedList 是用链表实现的，所以它没有用 RandomAccess 接口实现吧？

beautiful ~就是这样

咱瞅瞅 LinkedList 源码

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

果然，跟咱们设想的一样，没有实现 RandomAccess 接口

那为啥 LinkedList 接口使用 for 循环去遍历的时候，慢的不行呢？

咱们瞅瞅 LinkedList 在 get 元素时，都干了点儿啥

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

Node node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

在 get 方法中，主要调用了 node() 方法，因为 LinkedList 是双向链表，所以 if (index < (size >> 1)) 在判断 i 是在前半段还是后半段，如果是前半段就正序遍历，如果是在后半段那就倒序遍历，那么为什么使用 for 循环遍历 LinkedList 时，会这么慢？（好像离真相越来越近了

原因就在两个 for 循环之中，以第一个 for 循环为例

• get(0) ：直接拿到了node0 地址，然后拿到 node0 的数据

• get(1) ：先拿到 node0 地址，然后 i < index ，开始拿 node1 的地址，符合条件，然后去拿 node1 的数据

• get(2) ：先拿到 node0 的地址，然后 i < index ，拿到 node1 的地址， i < index ，继续向下走，拿到 node2 的地址，符合条件，获取 node2 的数据

发现问题了嘛？我就是想要 2 的数据， LinkedList 在遍历时，将 0 和 1 也给遍历了，如果数据量非常大的话，那效率可不就唰唰的下来了嘛

那到现在，咱们也就非常明确了，如果是要遍历 ArrayList 的话，最好是用 for 循环去做，如果要遍历 LinkedList 的话，最好是用迭代器去做

我猜你一定会说，阿粉啊，那如果对方就给我传过来了一个 list ，我不知道它是 ArrayList 还是 LinkedList 呀？我该怎么办呢

还记得 ArrayList 和 LinkedList 有什么不同吗？是不是 ArrayList 实现了 RandomAccess 接口，但是 LinkedList 没有实现，所以可以从这点去着手解决

暖暖的阿粉在这里给个简单的小 demo ，可以参考下:

public class ListTest {
    public static void main(String[] args) {
        List arrayList = new ArrayList();
        arrayList.add("aaa");
        arrayList.add("bbb");
        isUseIterator(arrayList);

        List linkedList = new LinkedList();
        linkedList.add("ccc");
        linkedList.add("ddd");
        isUseIterator(linkedList);
    }

    public static void isUseIterator(List list){
        if (list instanceof RandomAccess){
            System.out.println("实现了 RandomAccess 接口,使用 for 循环遍历");

            for (int i = 0 ; i < list.size(); i++ ){
                System.out.println(list.get(i));
            }
        }else{
            System.out.println("没有实现 RandomAccess 接口,使用迭代器遍历");

            Iterator it = list.iterator();
            while (it.hasNext()){
                System.out.println(it.next());
            }
        }
    }
}