黑马程序员技术交流社区

标题: ArrayList,和LinkedList的各自性能问题 [打印本页]

作者: 胡乃锋 时间: 2013-11-20 10:55
标题: ArrayList,和LinkedList的各自性能问题
他俩具体有啥区别啊，各自存储什么样的数据能展现各自的性能特点，说LinkedList是双向链表，双向链表存储优势在哪里啊

作者: 木木赤赤 时间: 2013-11-20 11:07
rrayList
ArrayList其实是包装了一个数组 Object[]，当实例化一个ArrayList时，一个数组也被实例化，当向ArrayList中添加对象是，数组的大小也相应的改变。这样就带来以下有缺点：
快速随即访问你可以随即访问每个元素而不用考虑性能问题，通过调用get(i)方法来访问下标为i的数组元素。
向其中添加对象速度慢当你创建数组是并不能确定其容量，所以当改变这个数组时就必须在内存中做很多事情。
操作其中对象的速度慢当你要想数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。

LinkedList
LinkedList是通过节点直接彼此连接来实现的。每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可，当删除记录时也一样。这样就带来以下有缺点：
操作其中对象的速度快只需要改变连接，新的节点可以在内存中的任何地方
不能随即访问虽然存在get()方法，但是这个方法是通过遍历接点来定位的所以速度慢

ArrayList：
本质上是使用数组存储的，所以是使用一段连续的存储单元依次存放所有的元素。
LinkedList：
是基于链表的，采用链式存储结构，用一组任意的存储单元存放所有元素。

ArrayList：
查找：O(1)
插入和删除：需要平均移动表长一半的元素，时间为O(n)。
LinkedList：
查找：O(n)
插入和删除：在指出需要插入或删除的结点的位置的情况下，时间为O(1)。

ArrayList：
需要预分配存储空间，当空间不足时，动态的增长。
LinkedList：
不需要分配存储空间，只需创建一个头结点header，随时根据需要把内存空间链接起来。

作者: 姚飞 时间: 2013-11-20 11:37
表示建议楼主仔细看下视频，老毕的视频里面有几个图画的非常好的，一目了然。。。2楼正解。。这个涉及到了数据结构，先把需要的学好。主次分明，以后有兴趣在弄。。。

作者: zy888802 时间: 2013-11-20 11:50
|--->ArrayList(JDK1.2):底层的数据结构是数组数据结构，特点是查询速度快(因为带角标)，
      但是增删速度稍慢,因为当元素多时，增删一个元素则所有元素的角标都得改变
      线程不同步。默认长度是10，当超过长度时，按50%延长集合长度。
|--->LinkedList(JDK1.2):底层数据结构式链表数据结构(即后面一个元素记录前一个)，
      特点：查询速度慢，因为每个元素只知道前面一个元素，但增删速度快
      因为元素再多，增删一个，只要让其前后的元素重新相连即可
      线程是不同步的。

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

黑马程序员IT技术论坛 X3.2