java ArrayList和LinkedList的区别

两种集合都被用来储存数据,那么区别在哪里?

 

ArrayList详解见:

https://zhuanlan.zhihu.com/p/24709456?refer=dreawer

LinkedList详解见:

https://zhuanlan.zhihu.com/p/24730576

只对比两者的基本区别,回顾一下之前没理解的概念(比如ArrayList中数组的扩容)。

一、不同之处

1.实现方式不同

(1)ArrayList

ArrayList通过动态数组实现,操作基于数组:

1

ArrayList使用的是“连续”(不是有序)的内存空间。

每个单元的大小和位置可以用简单的四则运算计算出来,比如每个节点占4bytes,存20个节点,就需要4*20=80bytes,第3个节点在4*3=第12个byte位置。

由于可以计算准确位置,这种结构在“随机存取操作”上很快,可以直接查第3个节点,就是第12个byte位置, a[3]或a.get(3)就返回第12byte位置起的数据代表的对象(这种方式就是简单的索引)。

在新增和删除操作中,由于是连续空间,插入数据需要对前后数据进行大块的整体搬移,空间不够时也需要整体扩容,删除后空间闲置需要整体回收。所以在删除新增操作上性能不佳。

(2)LinkedList

LinkedList通过双向链表实现,操作都基于链表:

1

双向链表不需要使用连续的内存空间,其每个节点都保存上一个和下一个节点的地址,就像火车和火车的各节车厢。

在插入时,把新车厢的前后固定点在原来的2个环的连接点之间简单对接上。

在删除时,拿掉一节车厢,直接把前一节和后一节首尾相连。因为仅对连接点操作,所以效率非常快,一步到位。

在查找时,需要从火车头顺序‘逐个’找到车尾(此说法有误,应该是从火车中部找到车厢所处的位置是前半部分/后半部分,再从头遍历/从尾遍历,具体见下文分析)。因为需要逐个检查,所以效率不佳。

2.不同的操作方法

(1)增加元素

1.ArrayList

ArrayList方法存在两种add方法,一种为直接add(e)把元素加入队尾。另一种add(index, element)把元素加入队中。

这两个方法都是向容器中添加新元素,这可能会导致数组空间不足,因此在添加元素之前,都需要使用ensureCapacityInternal方法检查剩余空间:

如果当前数组空间不够了,就调用grow方法扩容:

其实扩容就是创建一个更大的数组(保证有空间插入更多元素),将原数组中的成员复制到新数组中(保证原数据不变)。原数组不需要主动释放,会被GC回收。之后所有的集合操作都在新数组上进行。

那么问题来了:如果往数组中插入大量元素,就可能进行多次扩容,从而降低插入的效率。因此,当我们清楚知道业务数据量或者需要插入大量元素前,可以使用ensureCapacity方法手动增加ArrayList实例的容量,一步到位,从而减少扩容的次数。

ensureCapacity是ArrayList的方法,如果使用List接口的声明方式:

就无法使用此方法手动扩容。

空间的问题解决后,插入过程就显得非常简单。add(e)只需要在队尾直接插入元素即可,效率较高。

但是add(index, element)就要复杂很多,需要先移动原队列中的元素,再把新元素插入指定的位置(我理解为给index处腾出位置)。

这里最关键的是arraycopy方法,负责“移动”插入位置后面的元素,给index位置腾出空间(“移动”这个说法是不严谨的。一个元素要怎样“移动”到下一个元素的位置?要怎么解释这个“移动”的过程?)。

(这里有个问题,为什么java源码中arraycopy方法只有定义,却没有实现?我们可以看到arraycopy方法用了一个native来修饰,意思是本方法是由其它语言来实现的(一般是C或C++),所以java源码中没有具体实现代码)

虽然在java源码中看不到arraycopy方法的具体实现,我们可以推测arraycopy方法的作用:依次复制、插入位置及后面的数组元素,到后面一格,为插入位置腾出空间。此过程从队尾元素开始(如果从index位置后的第一个元素(队头)开始复制插入,会覆盖掉后面一格的指针)依次往后复制插入(这里操作的全部都是指针,或者说是引用),直到后面的元素全部“移动”完成,直接把index处的指针指向我们新插入的元素对象,完成插入操作。

因为ArrayList使用整块的内存空间,使用add(index, element)往往需要移动大量数据,所以从队中插入的效果可能不佳。

2.LinkedList

LinkedList底层通过双向链表实现,相比ArrayList,LinkedList不需要直接操作数组,同时也不需要关心数组的大小,增加操作只需要改变指针即可(就是数据结构中的基本操作)。

LinkedList存在两种add方法,一种为直接add(e)把元素加入队尾。另一种add(index, element)把元素加入队中。

既然是链表,当然保证链表不能断开(其中某一节点为空)。

这里的list中间缺少index = 1 的节点,所以报出java.lang.IndexOutOfBoundsException: Index: 2, Size: 1错误。

add(e)方法需要判断插入节点的位置,如果最后一个节点都不存在(即当前链表为空),就在第一个元素的位置插入节点。如果不为空,即链表不为空,则在最后一个节点后插入元素。

add(int index, E element)的逻辑更加复杂,可以分成两步:

(1)先根据index找到要插入的位置。

(2)修改引用,完成插入操作。

LinkedList的add只需要修改节点指针的指向即可,插入效率很高。

(2)获取某元素

1.ArrayList

ArrayList是基于索引的数据结构,它使用上文提到的索引在数组中搜索和读取数据。ArrayList的get方法只是从数组里面拿一个位置上的元素,获取数据的时间复杂度是O(1),所以效率很高,速度比较快。

2.LinkedList

LinkedList没有这么简单直接:

其中的node方法就是问题所在:

首先通过if (index < (size >> 1))计算index是在前半个链表还是后半个链表(这里的位运算往后位移一位,即size/2。如4的二进制位0100,往后移一位为0010,即2),之后遍历链表,分别正序遍历/倒序遍历,直至找到index位置的节点为止。

也就是说,LinkedList在get任何一个位置的数据的时候,都会顺着前面的数据去找,在这里花费了大量的时间,效率比ArrayList中更差。

这个问题在for循环中体现得更加明显(多次操作导致差距变大),所以不要使用for循环遍历LinkedList获取元素。具体可以参考:

java 为什么遍历LinkedList要使用迭代器/foreach?

想要遍历LinkedList获取元素,应该使用迭代器或者foreach循环(foreach循环的原理就是迭代器)。迭代器方式直接按照地址去查找数据,将大大提升遍历LinkedList的效率。

至于迭代器的实现原理,我们在之后的文章中讨论。

感谢:http://www.cnblogs.com/zhilu-doc/p/5292818.html

3.适用场景不同

对两种结合的读写性能进行了一些测试:

测试结果太麻烦,不贴了。测试的结果与数据量和数据的插入位置紧密相关,这里的结论只是简单结论,建议实际使用的时候根据具体情况实验。

我的结论是:

(1)在数据量不大时(大概1w),插入位置1000(集合前部),ArrayList读性能强于LinkedList,写性能和LinkedList相差无几。

(2)在数据量不大时(大概1w),插入位置5000(集合中部),ArrayList读写性能均强于LinkedList。

(3)在数据量不大时(大概1w),插入位置9000(集合后部),ArrayList读写性能均强于LinkedList。

(4)在数据量较大时(大概10w),插入位置10000(集合前部),ArrayList读性能强于LinkedList,写性能两者相近。

(5)在数据量较大时(大概10w),插入位置50000(集合前部),ArrayList读性能强于LinkedList,写性能弱于LinkedList。

(6)在数据量较大时(大概10w),插入位置90000(集合前部),ArrayList读性能强于LinkedList,写性能弱于LinkedList。

其他数值未测试。具体情况需要具体分析。

二、总结

复习一下。

发表评论

电子邮件地址不会被公开。 必填项已用*标注