ArrayList和LinkedList的区别

1. 数据结构不同

ArrayList是基于动态数组实现的。

LinkedList是基于双向链表实现的。

2. 效率不同

随机访问

随机访问(get或set)，ArrayList比LinkedList效率高。因为LinkedList要移动指针进行查找。

LinkedList在查找过程中会先确定当前要访问的index处于前半部分还是后半部分，然后在从头或尾开始查找。

添加元素

添加元素又分为是随机位置添加还是只向尾部添加。

如果是只向尾部添加，在给定合适大小的数组中，不发生扩容的情况下ArrayList的性能要好一些。

在集合头部添加，LinkedList的性能更好，因为ArrayList需要进行数组的复制和重排。

删除元素

删除元素LinkedList主要影响性能的点是在找要删除的元素，ArrayList主要影响性能的点是在删除后数组的移动重组。

遍历

Arraylist实现了RandomAccess接口，遍历速度快。

LinkedList通过for循环遍历慢，可以通过迭代器遍历。

3. 实现接口

LinkedList实现了Deque接口，可以做为双端队列或栈使用。