ArrayList和LinkedList的相同点
1、ArrayList和LinkedList都是List接口的实现类，有共同的父类AbstractList和AbstractCollection；
2、两者其中存储的数据有序，值允许重复；
3、可以插入多个null元素；
4、都是非线程安全的。
ArrayList和LinkedList的区别
1. ArrayList的实现是基于数组,LinkedList的实现是基于双向链表。
2. 对于随机访问ArrayList要优于LinkedList,ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问,而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起,查找某个元素的时间复杂度是O(N)。
3. 对于插入和删除操作,LinkedList要优于ArrayList,因为当元素被添加到LinkedList任意位置的时候,不需要像ArrayList那样重新计算大小或者是更新索引。
4. LinkedList比ArrayList更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。
接下来我们再看看两者性能的区别。
ArrayList和LinkedList的性能区别
首先对比下常用操作的算法复杂度
LinkedList
- get(int index) : O(n)
- add(E element) : O(1)
- add(int index, E element) : O(n)
- remove(int index) : O(n)
- Iterator.remove() : O(1) <— LinkedList的主要优点
- ListIterator.add(E element) is O(1) <— LinkedList的主要优点
ArrayList
- get(int index) : O(1) <— ArrayList的主要优点
- add(E element) : 基本是O(1) , 因为动态扩容的关系，最差时是 O(n)
- add(int index, E element) : 基本是O( n – index) , 因为动态扩容的关系，最差时是 O(n)
- remove(int index) : O(n – index) (例如，移除最后一个元素，是 O(1))
- Iterator.remove() : O(n – index)
- ListIterator.add(E element) : O(n – index)
- LinkedList，因为本质是个链表，所以通过Iterator来插入和移除操作的耗时，都是个恒量，但如果要获取某个位置的元素，则要做指针遍历。因此，get操作的耗时会跟List长度有关
对于ArrayList来说，得益于快速随机访问的特性，获取任意位置元素的耗时，是常量的。
但是，如果是add或者remove操作，要分两种情况，如果是在尾部做add，也就是执行add方法（没有index参数），此时不需要移动其他元素，耗时是O(1),但如果不是在尾部做add，也就是执行add(int index, E element),这时候在插入新元素的同时，也要移动该位置后面的所有元素，以为新元素腾出位置，此时耗时是O(n-index)。
另外，当List长度超过初始化容量时，会自动生成一个新的array(长度是之前的1.5倍),此时会将旧的array移动到新的array上，这种情况下的耗时是O(n)。
总之，get操作，ArrayList快一些，而add操作，两者差不多。
除非是你希望在List中间插入节点，且维护了一个Iterator指向指定位置，这时候linkedList能快一些，但是，我们更多时候是直接在尾部插入节点，这种特例的情况并不多。
空间占用上
ArrayList完胜
看下两者的内存占用图
这三个图，横轴是list长度，纵轴是内存占用值，两条蓝线是LinkedList，两条红线是ArrayList。
可以看到，LinkedList的空间占用，要远超ArrayList。
LinkedList的线更陡，随着List长度的扩大，所占用的空间要比同长度的ArrayList大得多。
注：从JDK6之后，默认启用了CompressedOops ，因此64位及32位下的结果没有差异，LinkedList x64和LinkedList x32的线是一样的。
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读更多mikechen架构文章👇
阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师
以上
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》