关于ArrayList与LinkedList问题

Question

想问一下，为什么说LinkedList的插入和删除性能比ArrayList好，而ArrayList的查询更好？

Answer 1

对于处理一列数据项，Java 提供了两个类ArrayList 和LinkedList ，ArrayList 的内部实现是基于内部数组Object[] ，从概念上讲，它更像数组，但LinkedList 的内部实现是基于一组连接的记录，所以，它更像一个链表结构，它们在性能上有很大的差别。
ArrayList和LinkedList都实现了List接口，ArrayList的实现用的是数组，LinkedList是基于链表，ArrayList适合查找，LinkedList适合增删。

ArrayList与LinkList两者的区别：

ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。
相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。
2) 相对于 ArrayList ， LinkedList 插入是更快的。因为 LinkedList 不像 ArrayList 一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是 ArrayList 最坏的一种情况，时间复杂度是 O(n) ，而 LinkedList 中插入或删除的时间复杂度仅为 O(1) 。 ArrayList 在插入数据时还需要更新索引（除了插入数组的尾部）。
3) 类似于插入数据，删除数据时， LinkedList 也优于 ArrayList 。
4) LinkedList 需要更多的内存，因为 ArrayList 的每个索引的位置是实际的数据，而 LinkedList 中的每个节点中存储的是实际的数据和前后节点的位置 ( 一个 LinkedList 实例存储了两个值： Node<E> first 和 Node<E> last 分别表示链表的其实节点和尾节点，每个 Node 实例存储了三个值： E item,Node next,Node pre) 。

什么场景下更适宜使用 LinkedList，而不用ArrayList
1) 你的应用不会随机访问数据 。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。
2) 你的应用更多的插入和删除元素，更少的读取数据 。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。

Answer 2

2者区别也并不是‘顺序’或‘有序’，而是本身的结构决定的：
Java SE提供的LinkedList其实是一种双向链表，每个节点都保存上一个和下一个节点的地址。
双向链表就像火车和火车的各节车厢。在插入时，把新车厢的前后固定点在原来的2个环的连接点之间简单对接上。而删除时，拿掉一节车厢，直接把前一节和后一节首尾相连。所以仅对连接点操作，效率非常快。只需一次。查找时，就需要从火车头顺序‘逐个’找到车尾，这种逐个检查所以查找效率不佳。

ArrayList使用的是‘连续’(不是有序)的内存空间。每个单元的大小和位置可以用简单的四则运算计算出来，比如每个节点占4bytes，存20个节点，就需要4*20=80bytes，第3个节点在4*3=第12个byte位置。由于可以计算准确位置，这种结构在'随机存取操作'上很快，可以直接查第3个节点，就是第12个byte位置, a[3]或a.get(3)就返回第12byte位置起的数据代表的对象。这种随机操作的便捷就是应用意义上的查找便捷。在新增和删除操作中，由于是连续空间，插入数据需要对前后数据进行大块的整体搬移，空间不够时也需要整体扩容，删除后空间闲置需要整体回收。所以在删除新增操作上性能不佳。

Answer 3

ArrayList类似于数组，是按顺序存储在内存的。
LinkedList类似与链表，是没有顺序的，是通过指针链接了每个元素。
因为LinkedList是无序存储的，所以插入随便一个地方都可以，只要指针指向了就行。
而ArrayList是有序的，插入要遍历到你要插入的位置，所以效率低些。
正因为ArrayList是有序的，所以查询的时候输入索引，就可以很快找到，LinkedList则不然。本回答被提问者和网友采纳