黑马程序员技术交流社区

标题: Arraylist和LinkedList的效率比较 [打印本页]
作者: 2012    时间: 2013-9-15 09:51
标题: Arraylist和LinkedList的效率比较
本帖最后由 杨增坤 于 2013-9-16 11:30 编辑

我看了很多资料或者博客，他们都提到了Arraylist查询遍历的时候，比LinkedList性能高，而在插入和删除的时候，Linkedlist又比arraylist性能高。
我想问一下具体的原因，他们的底层是怎么实现的？
难道仅仅是因为一个是数组，一个是链表吗？
希望大牛们能给我点建议。谢谢
作者: Michael_xpd    时间: 2013-9-15 10:08
      对于处理一列数据项， Java 提供了两个类 ArrayList 和 LinkedList ， ArrayList 的内部实现是基于内部数组 Object[] ，所以从概念上讲，它更像数组，但 LinkedList 的内部实现是基于一组连接的记录，所以，它更像一个链表结构，所以，它们在性能上有很大的差别。
     ArrayList 的查询效率比较高，增删动作的效率比较差，适用于查询比较频繁，增删动作较少的元素管理的集合。 LinkedList 的查询效率低，但是增删效率很高。适用于增删动作的比较频繁，查询次数较少的元素管理集合。
作者: 2012    时间: 2013-9-15 10:12
Michael_xpd 发表于 2013-9-15 10:08
对于处理一列数据项， Java 提供了两个类 ArrayList 和 LinkedList ， ArrayList 的内部实现是基于内 ...

大部分的博客也是这样说的，兄弟我很想知道他们的底层是怎么实现的，能给我讲解一下吗？谢谢
作者: 冷漠无天    时间: 2013-9-15 10:41
1.ArrayList是由一个数组后推得到的；而LinkedList是根据常规的双重链接列表方式实现的，因为每个单独的对象都包含了数据以及指向列表内前后元素的句柄。正是由于这个原因，假如想在一个列表中部进行大量插入和删除操作，那么LinkedList无疑是最恰当的选择。若非如此，就情愿选择ArrayList，它的速度可能要快一些。
2。在ArrayList中进行随机访问（即get()）以及循环反复是最划得来的；但对于LinkedList却是一个不小的开销。但另一方面，在列表中部进行插入和删除操作对于LinkedList来说却比ArrayList划算得多。我们最好的做法也许是先选择一个ArrayList作为自己的默认起点。以后若发现由于大量的插入和删除造成了性能的降低，再考虑换成LinkedList不迟。
作者: 陈国柱    时间: 2013-9-15 11:52
ArrayList：底层的数据结构使用的是数据结构,查询的时候不用判断元素，只需要通过每个元素的角标就可以了，因而会查询速度快；而增加和删除元素的时候，往往会造成其他元素的角标的改动，因而会造成速度较慢。
LinkedList：底层使用的是链表数据结构，可以看成每个元素之间都有一根线连接起来，查询的时候，要重头开始遍历元素，直到找到为止，因而速度较慢；而增加元素的时候，只需要断开需要插入元素位置附近两个元素之间的连线，然后插入元素即可，删除的做法想反，因而会使得增删速度较快。
作者: 雪龙    时间: 2013-9-15 12:01
本帖最后由 雪龙 于 2013-9-15 12:13 编辑
陈国柱 发表于 2013-9-15 11:52
ArrayList：底层的数据结构使用的是数据结构,查询的时候不用判断元素，只需要通过每个元素的角标就可以了， ...

我很赞同楼上的意见 ，在里再做一点补充，希望能更好的解决楼主的问题
ArrayList：底层的数据结构使用的是数组结构,查询元素的可以直接根据角标去找对应的元素，并且数组在存储的时候往往是存储在一块区域，因而会查询速度快；而增加和删除元素的时候，一般需要先找到增加和删除元素的位置，如果增加的话，这个元素之后的所有元素的角标都要加1，如果删除的话，这个元素之后的所有元素的角标减1.举两个极端的例子如果都在第一个元素的位置增加和删除，可以想象会有多大的开销。


LinkedList：底层使用的是链表数据结构，并且这些数据在存储的时候不是连续的内存空间，而是由一根线将这些元素连接起来，可以这样想，在每个元素之后存储的是下一个元素的地址，和上一个元素的地址，这样在查询的时候，要重头开始遍历元素，由上一个元素找下一个元素，直到找到为止，因而速度较慢；而增加元素的时候，只需要断开需要插入元素位置附近两个元素之间的连线，也就是改变前后两个元素的对于要删除或插入元素的地址即可，因而会使得增删速度较快。




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2