侧边栏壁纸
博主头像
Lang博主等级

十七岁想打职业。

  • 累计撰写 10 篇文章
  • 累计创建 11 个标签
  • 累计收到 1 条评论
隐藏侧边栏

ArrayList与LinkedList区别

Lang
2022-02-08 / 0 评论 / 0 点赞 / 379 阅读 / 3,483 字
温馨提示:
本文最后更新于 2022-02-08,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

先上结论:
ArrayList与LinkedList都实现了List接口。

  1. ArrayList底层是数组,查询快、增删慢;
  2. LinkedList底层是链表,查询慢、增删快。

样例一(增删)

代码验证:

两个插入,看运行结果耗时似乎差别也不是很大,难道结论有问题?

代码改造一下 add方法中添加插入索引,从每次从尾部追加改为每次从头部追加。

差异显著,也验证了结论:ArrayList增删比LinkedList慢的多。
源码如下:

public class Test {

    public static void main(String[] args) {

        int num = 100000;

        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        long l1 = System.currentTimeMillis();
        for (int i = 0; i < num; i++) {
            arrayList.add(0,i);
        }
        long l2 = System.currentTimeMillis();
        System.out.println("ArrayList添加"+num+"数据耗时:" + (l2 - l1));
        for (int i = 0; i < num; i++) {
            linkedList.add(0,i);
        }
        long l3 = System.currentTimeMillis();
        System.out.println("LinkedList添加"+num+"数据耗时:" + (l3 - l2));
    }

}

样例二(查询)

代码验证:

我们先每次查询第一条元素,结果却是耗时差不多。

我们再改成遍历查询每一条元素,结果差异明显。也印证了我们的结论:ArrayList查询速度比LinkedList快。

源码如下:

public class Test {

    public static void main(String[] args) {
        int num = 100000;
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < num; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        long l1 = System.currentTimeMillis();
        for (int i = 0; i < num; i++) {
            arrayList.get(0);
        }
        long l2 = System.currentTimeMillis();
        System.out.println("ArrayList查询"+num+"数据耗时:" + (l2 - l1));
        for (int i = 0; i < num; i++) {
            linkedList.get(0);
        }
        long l3 = System.currentTimeMillis();
        System.out.println("LinkedList查询"+num+"数据耗时:" + (l3 - l2));
    }
}

看完两个样例,总会有些疑问,在某些情况下ArrayList与LinkedList的结论似乎有些不对,或者为啥会出现这样的结果,这些疑问就需要一起看看源码吧。

ArrayList源码

1.增加元素

我们知道ArrayList的底层是数组。

再看构造方法,在我们未声明集合大小时,默认是一个空数组。

接下来看看add方法 ensureCapacityInternal:确保数组不会越界,当超出数组长度需要扩容。传入的值size+1,size表示当前集合的存储的元素数量,+1保证再放一个元素也能容纳。
多说一句:数组是定长的,elementData[index] 当index大于elementData.length的时候就会报数组越界,所以为避免数组越界需要重新声明一个长度更长的数组存储。当然如果一开始声明特别长度特别长的数组就会造成资源浪费,会开辟不必要的内存空间。这里也是。ArrayList数组默认长度是10,而jdk1.8时,构造器中初始化的是一个空的数组,只有在add方法调用的时候才会初始化,创建长度10的数组。

我们跟进ensureCapacityInternal方法,calculateCapacity获取到最小的数组长度,默认的是10。ensureExplicitCapacity方法中最小长度大于当前数组长度就需要扩容了,也就是调用grow方法。

核心扩容方法,扩容的后的大小为int newCapacity = oldCapacity + (oldCapacity >> 1); >>1 右移1位 也就是除二,也就是扩容到原来的1.5倍。Arrays.copyOf方法意思是将老数组复制到新数组,参数一为老数组,参数二为新数组长度,返回参数为新数组。注意真正耗费时间的是这个数组重新复制的过程。所以我们能理解:一次add如果不触发扩容grow方法是不怎么耗时间的。而每次扩容到原来的1.5倍大小,数组越大就越难触发扩容。 所以我们能理解样例一中第一个截图为啥ArrayList的add并没有那么耗时。

再看样例一截图二,add(int index, E element) 方法,rangeCheckForAdd会先判断传入的下标是否越界。ensureCapacityInternal在判断是否需要扩容。System.arraycopy就是整个耗时的罪魁祸首,插入时需要把当前下标及以后的元素往后移动一位。介绍一下System.arraycopy:参数一代表源数组,参数二代表源数组要复制的起始位置,参数三代表目标数组,参数四代表目标数组复制的起始位置,参数五代表复制的长度。这一个移动位置的过程是非常消耗时间的,而且样例一截图二中每一次都是从0开始插入也就是每一次都要移动位置。这就是为啥这个耗时间。其实add(int index, E element)才是语义上的插入,add(E element)只能说是追加。所以结论还是没错,ArrayList插入慢。

2.查询元素

至于为啥ArrayList查询快,数组根据下标找自然快。

LinkedList源码

我们解释了样例一,接下来样例二要从LinkedList源码中找答案。

1.增加元素

Node就是代表链表中的一个节点,两个Node一个头部节点,一个尾部节点。构造方法为空。

item节点上存储的元素,next,prev代表双节点,记录了上一节点和下一节点。

先看add方法,添加到尾部只是创建了一个节点Node然后将上一节点指向新创建的节点。不耗时。

add(int index, E element) 方法如果不是尾部插入,则调用了linkBefore。

此时根据下标index找节点的方法node是要花费一些时间的,但因为是双节点,最多遍历的次数也就长度的一半。先判断下标index是否大于集合长度一半,大于则从尾部找,小于则从头部找。

找到原先index所在的节点后,创建新节点,重新指向前后节点。所以整个过程不咋耗时间,因为样例一截图二add的index用的是0 找节点过程也基本不耗时。

2.查询元素

此时我们就能理解样例二截图一中为啥get(0)1000000次不咋耗时间,因为每次都是取第0个元素,node方法中遍历第一个就找到了。为啥截图二get(i)却很耗时间,越靠近中间遍历的次数就越多,消耗的时间也就越多了。

总结

重申结论

  1. ArrayList底层是数组,查询快、增删慢;
  2. LinkedList底层是链表,查询慢、增删快。

从查看源码我们得到一些结论:

  1. ArrayList默认容量是10
  2. ArrayList扩容大小为原来的1.5倍
  3. 声明ArrayList时,知道大小的前提下建议声明大小,避免扩容耗费时间。
  4. ArrayList add(int index, E element) 插入慢的原因是需要复制数组移位置以及扩容。
  5. LinkedList add(int index, E element)极端情况下也是会耗时间的。
  6. LinkedList 内部维护了一个节点Node类
  7. LinkedList 是双向链表,减少查询速度,但会增加存储节点成本,空间换时间。
0

评论