黑马程序员技术交流社区

标题: 什么时候用LinkedList，什么时候用ArrayList？ [打印本页]

---

作者: zhao543    时间: 2017-3-7 19:36
标题: 什么时候用LinkedList，什么时候用ArrayList？

ArrayList是使用数组实现的list，本质上就是数组。ArrayList中的元素可以通过索引随机获取一个元素。但是如果该数组已满，当添加新元素时需要分配一个新的数组然后将原来数组的元素移动过去，需要O(n)的时间复杂度。添加或删除一个元素需要移动数组中的其他元素。这是ArrayList最大的缺点。

LinkedList是一个双向链表。因此，当需要获取list中某个元素，需要从头到尾遍历list。另一方面，在链表中添加或删除元素很快，只需要O(1)的时间复杂度。从空间上来说，在链表中一个节点需要两个额外的指针来指向它的previous和next节点。

总结：

从时间复杂度来说，如果对list增加或删除操作较多，优先用LinkedList；如果查询操作较多，优先用ArrayList。

从空间复杂度来说，LinkedList会占用较多空间。

---

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

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