本文引用自霍格沃兹测试开发学社录播课
Java经典面试题-ArrayList、LinkedList 区别
霍格沃兹测试开发
http://ceshiren.com
面试相关问题
- List集合常见实现类有哪些？
- ArrayList、LinkedList 有什么区别？
- 数组和链表的区别？
- Java中快速查找业务使用哪种类型数据结构？
- Java中增删频繁的业务推荐使用哪种类型数据结构？
面试考察点分析
- List集合是否了解
- 数组、链表是否了解
共同点
- ArrayList、LinkedList 都实现了 List 接口
- 对应的List的方法都可以使用，只不过实现类的底层的实现逻辑不同
- 都允许有重复元素、有先后放入次序
- 都可以位置（索引）访问，元素的添加、删除，迭代器遍历
不同点
- 底层数据结构
- 构造方法
- 添加元素
- 获取
- 遍历
1. 底层数据结构不同
-
ArrayList底层- Object 数组
-
LinkedList底层- 双向链表的Node结点
构造方法不同
-
ArrayList- 指定空间大小构造方法
- 无参构造
-
LinkedList- 无参构造
添加元素不同
- ArrayList
- 动态扩容1.5倍
- LinkedList
- 遍历查找添加
当两者的起始长度一样
-
ArrayList、LinkedList 长度固定，且添加元素时不涉及扩容，性能进行对比：
- ArrayList 在==中间位置新增元素==、==尾部新增元素==时性能比 LinkedList 好很多
- ArrayList只有==头部新增元素==的时候比 LinkedList 差
- 因为数组复制的原因
根据下标获取元素
- ArrayList 直接返回数组元素
- LinkedList 需要集合分前后2个半段遍历
根据元素获取下标
- ArrayList 返回最小的索引，没有返回-1
- LinkedList 需要遍历
遍历不同
- for 循环遍历的时候，ArrayList 花费的时间远小于 LinkedList
- 迭代器遍历的时候，两者性能差不多
遍历时间
| 5000个 | for循环遍历时间 | 迭代器遍历时间 | for循环遍历时间 | 迭代器遍历时间 |
|---|---|---|---|---|
| ArrayList | 0 | 1 | 1 | 3 |
| LinkedList | 21 | 2 | 20 | 1 |
总结
面试官可能会问：ArrayList 和 LinkedList 的区别是什么？
- ArrayList 和 LinkedList 存储的数据都是线性存储，元素可重复，并且有先后放入次序；
- ArrayList 底层数据结构为数组，可进行动态扩容，每次扩容1.5倍，非常适合随机访问的业务场景
- LinkedList 底层数据结构为节点，不是一个连续的，非常适合元素插入、删除的业务场景: