目录
- 一、有一道经典的面试题，“ArrayList 和 LinkedList 的区别是什么？”
- 1、小白答法：
- 2、入门答法：
- 3、系统回答
- 二、LinkedList的插入速度一定比ArrayList快吗？
- 三、分析一下两种数据结构的add源码
- 1、先分析熟悉的ArrayList
- 2、LinkedList源码
大家好，我是哪吒。
一、有一道经典的面试题，“ArrayList 和 LinkedList 的区别是什么？”
1、小白答法：
- ArrayList是动态数组的数据结构实现，查找和遍历的效率较高；
- LinkedList 是双向链表的数据结构，增加和删除的效率较高；
2、入门答法：
ArrayList 底层是基于数组实现的，ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。
LinkedList 底层是基于链表实现的，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。 正因为底层数据结构的不同，他们适用的场景不同，ArrayList 更适合随机查找，LinkedList 更适合删除和添加，查询、添加、删除的时间复杂度不同。
3、系统回答
ArrayList和LinkedList都是Java中实现了List接口的常用数据结构，它们的主要区别体现在以下四个方面：
- 底层数据结构：ArrayList基于动态数组实现，而LinkedList则是基于链表实现。
- 内存空间开销：ArrayList在List列表中预留了一定空间，而LinkedList则需要存储节点信息及指针信息。
- 随机访问效率：ArrayList可以通过索引直接访问元素，效率较高；而LinkedList则是线性的数据存储方式，只能从前往后移动指针依次查找，速度较慢。
- 增删操作效率：在进行元素的增加和删除操作时，由于ArrayList需要移动元素，效率较低；而LinkedList只需更改指针即可完成操作，效率较高。
综上所述，ArrayList和LinkedList各有优劣，需要根据实际需求来选择使用哪种数据结构。
核心观点，就是ArrayList适合查找和遍历，LinkedList 适合增加和删除，我总结的应该没错吧。
二、LinkedList的插入速度一定比ArrayList快吗？
做一个实验：
private static void test(int n){
StopWatch stopWatch = new StopWatch();
stopWatch.start();
List<String> arrayList = new ArrayList<>();
for (int i = 0; i < n; i++) {
arrayList.add(UUID.randomUUID().toString());
}
stopWatch.stop();
System.out.println("ArrayList添加"+n/10000+"万个字符串耗时："+stopWatch.getTotalTimeSeconds());
StopWatch stopWatch1 = new StopWatch();
stopWatch1.start();
List<String> linkedList = new LinkedList<>();
for (int i = 0; i < n; i++) {
linkedList.add(UUID.randomUUID().toString());
}
stopWatch1.stop();
System.out.println("LinkedList添加"+n/10000+"万个字符串耗时："+stopWatch1.getTotalTimeSeconds());
System.out.println("-----------------------------");
}
随着add数量级的暴增，LinkedList的插入速度与ArrayList的插入速度在逐渐接近。
三、分析一下两种数据结构的add源码
1、先分析熟悉的ArrayList
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
2、LinkedList源码
LinkedList 是基于链表实现的结构，主要核心是 Node 节点。
add(E e) 是在链表的尾部添加数据。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
// 记录原尾部节点
final Node<E> l = last;
// 创建新节点，新节点的前置节点为原尾部节点
final Node<E> newNode = new Node<>(l, e, null);
// 更新尾部节点
last = newNode;
if (l == null)
// 尾部节点为空，更新头部节点
first = newNode;
else
// 尾部不为空，原尾部后置节点就是新节点
l.next = newNode;
size++;
modCount++;
}
这是一个双链表的结构，有 prev 前置指针和next 后置指针。
还有首节点first、尾节点last、长度size：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
🏆哪吒多年工作总结：Java学习路线总结，搬砖工逆袭Java架构师。
