LinkedList的插入速度一定比ArrayList快吗？

速度一定比ArrayList快吗？"/>

LinkedList的插入速度一定比ArrayList快吗？

目录

• • 一、有一道经典的面试题，“ArrayList 和 LinkedList 的区别是什么？”
  • • 1、小白答法：
    • 2、入门答法：
    • 3、系统回答
  • 二、LinkedList的插入速度一定比ArrayList快吗？
  • 三、分析一下两种数据结构的add源码
  • • 1、先分析熟悉的ArrayList
    • 2、LinkedList源码

大家好，我是哪吒。

一、有一道经典的面试题，“ArrayList 和 LinkedList 的区别是什么？”

1、小白答法：

1. ArrayList是动态数组的数据结构实现，查找和遍历的效率较高；
2. LinkedList 是双向链表的数据结构，增加和删除的效率较高；

2、入门答法：

ArrayList 底层是基于数组实现的，ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。

LinkedList 底层是基于链表实现的，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。 正因为底层数据结构的不同，他们适用的场景不同，ArrayList 更适合随机查找，LinkedList 更适合删除和添加，查询、添加、删除的时间复杂度不同。

3、系统回答

ArrayList和LinkedList都是Java中实现了List接口的常用数据结构，它们的主要区别体现在以下四个方面：

1. 底层数据结构：ArrayList基于动态数组实现，而LinkedList则是基于链表实现。
2. 内存空间开销：ArrayList在List列表中预留了一定空间，而LinkedList则需要存储节点信息及指针信息。
3. 随机访问效率：ArrayList可以通过索引直接访问元素，效率较高；而LinkedList则是线性的数据存储方式，只能从前往后移动指针依次查找，速度较慢。
4. 增删操作效率：在进行元素的增加和删除操作时，由于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架构师。