黑马程序员技术交流社区

标题: 集合的比较 [打印本页]

作者: 刘江华 时间: 2011-10-22 14:49
标题: 集合的比较
谁说下集合中 linkedList 和ArrayList执行效率的比较，以及分析下它们的数据结构方式。谢谢。

作者: 郭敏 时间: 2011-10-22 14:53
| ---- ArrayList: 底层的数据结构使用的数组数据结构。特点：查询，修改数据比较快，但是增删稍慢。线程不同步。默认长度为10 按50%增长
| ---- LinkedList: 底层的数据结构使用的是链表数据结构。特点：增删速度很快，查询稍慢。

作者: 想好了再写 时间: 2011-10-22 19:14
总的来说ArrayList和LinkedList的大致区别：
   1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
   2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
   3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
详细来说ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素就是挨个比较查找。然而当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的（这个例子有点极端，但是能说明问题）
还有HashList在删除插入和查找上的效率跟开销都是在两个之间的，不是很好也不是很坏，可以根据你要做的东西选择要用哪一种。一般情况下如果经常要进行删除插入操作的话选用LinkedList，而如果做的项目要经常对数据进行查找操作最好选用ArrayList，而如果也要做删除插入操作也做查找操作的话，就用HashList吧

作者: 咖啡 时间: 2011-10-22 22:00
多看下毕老师的视频，就知道了啦

作者: 刘江华 时间: 2011-10-23 16:14
我去找找看那视频。谢谢各位了。{:soso_e179:}

作者: 杨强 时间: 2011-10-24 19:57
1)Linkedlist效率当然是高的, 你就算优化到极致, 估计也差别不大;
2)ArrayList当然比数组的效率低一些, 毕竟是多了一些环节, 但ArrayList用着方便, 它相当于一个可变长度的数组;
3)折半插入排序算法;
4)ArrayList主要是查找快速
5)LinkedList主要是增刪快速

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

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