文
章
目
录
章
目
录
本文主要讲解关于Java集合常会被问到的面试题：ArrayList和LinkedList的相同点与不同点相关内容，让我们来一起学习下吧！
友情提示：LinkedList其实就是数据结构中的双向链表，没学过的话可以学一下有关链表的知识，至于LinkedList中的源码其实大多数据结构的基本链表操作实现的，这里我就不多做说明了，有兴趣的话可自行看源码
由于ArrayList由动态数组实现，LinkedList由双向链表实现，这里将它们的对比归类于数组与链表的区别
一、相同点
- 数组和链表都是线性表，所谓线性，即结构像一条直线一样；
- 这与非线性结构是不一样的，例如二叉树，它的结构是一个树状图，那必然不是线性的
二、不同点
1）在空间上
- 数组使用连续空间存储，且数组容量往往会大于数据存储量，这就会有空间浪费
- 链表（多个链表节点）使用非连续的空间，通过链表节点地址连接，对空间利用率很高
2）在时间上
- 按下标查询时数组查询数据时（get方法）直接根据下标访问，时间复杂度为O(1)
链表查询数据时需要从头节点查找一直到找到目标元素，时间复杂度为O(n)
- 添加或删除时数组添加（而且添加有扩容操作）和删除时找到目标元素后需要移动目标元素后面的所有元素，也就是对后面的元素都需要操作一次，那么时间复杂度为O(n)
链表添加和删除时链表找到目标节点后可以直接改变next和pre指向，时间复杂度为O(1)
所以在多用查询操作时选择数组效率更高，在使用添加和删除操作频繁时选择链表效率更高。
以上就是关于Java集合常会被问到的面试题：ArrayList和LinkedList的相同点与不同点相关的全部内容，希望对你有帮助。欢迎持续关注潘子夜个人博客（www.panziye.com），学习愉快哦！
