面试官问我，LinkedList真的是查找慢增删快吗？确认吗？
来源：blog.csdn.net/dearKundy/article/details/84663512
# 测试结果
废话不多说，先上测试结果。作者分别在ArrayList和LinkedList的头部、尾部和中间三个位置插入与查找100000个元素所消耗的时间来进行对比测试，下面是测试结果
测试结论
# 源码分析
我们把Java中的ArrayList和LinkedList就是分别对顺序表和双向链表的一种实现，所以在进行源码分析之前，我们先来简单回顾一下数据结构中的顺序表与双向链表中的关键概念
所以我们潜意识会认为：ArrayList查找快，增删慢。LinkedList查找慢，增删快。但实际上真的是这样的吗？我们一起来看看吧。
测试程序
测试程序代码基本没有什么营养，这里就不贴出来了，但是得把程序的运行结果贴出来，方便逐个分析。
运行结果
ArrayList尾部插入100000个元素耗时：26ms
LinkedList尾部插入100000个元素耗时：28ms
ArrayList头部插入100000个元素耗时：859ms
LinkedList头部插入100000个元素耗时：15ms
ArrayList中间插入100000个元素耗时：1848ms
LinkedList中间插入100000个元素耗时：15981ms
ArrayList头部读取100000个元素耗时：7ms
LinkedList头部读取100000个元素耗时：11ms
ArrayList尾部读取100000个元素耗时：12ms
LinkedList尾部读取100000个元素耗时：9ms
ArrayList中间读取100000个元素耗时：13ms
LinkedList中间读取100000个元素耗时：34928ms
# ArrayList尾部插入
源码
add(E e)方法
public boolean add(E e) {// 检查是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!!// 直接在尾部添加元素 elementData[size++] = e;return true; }可以看出，对ArrayList的尾部插入，直接插入即可，无须额外的操作。
# LinkedList尾部插入
源码
LinkedList中定义了头尾节点
/** * Pointer to first node. */ transient Node<E> first;
/** * Pointer to last node. */ transient Node<E> last;add(E e)方法，该方法中调用了linkLast(E e)方法
public boolean add(E e) { linkLast(e);return true; }linkLast(E e)方法，可以看出，在尾部插入的时候，并不需要从头开始遍历整个链表，因为已经事先保存了尾结点，所以可以直接在尾结点后面插入元素
/** * Links e as last element. */void linkLast(E e) {// 先把原来的尾结点保存下来final Node<E> l = last;// 创建一个新的结点，其头结点指向lastfinal Node<E> newNode = new Node<>(l, e, null);// 尾结点置为newNode last = newNode;if (l == null) first = newNode;else// 修改原先的尾结点的尾结点，使其指向新的尾结点 l.next = newNode; size++; modCount++; }总结
对于尾部插入而言，ArrayList与LinkedList的性能几乎是一致的
# ArrayList头部插入
源码
add(int index, E element)方法，可以看到通过调用系统的数组复制方法来实现了元素的移动。所以，插入的位置越靠前，需要移动的元素就会越多
public void add(int index, E element) { rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!// 把原来数组中的index位置开始的元素全部复制到index+1开始的位置（其实就是index后面的元素向后移动一位） System.arraycopy(elementData, index, elementData, index + 1, size - index);// 插入元素 elementData[index] = element; size++; }# LinkedList头部插入
源码
add(int index, E element)方法，该方法先判断是否是在尾部插入，如果是调用linkLast()方法，否则调用linkBefore()，那么是否真的就是需要重头开始遍历呢？我们一起来看看
public void add(int index, E element) { checkPositionIndex(index);
if (index == size) linkLast(element);else linkBefore(element, node(index)); }在头尾以外的位置插入元素当然得找出这个位置在哪里，这里面的node()方法就是关键所在，这个函数的作用就是根据索引查找元素，但是它会先判断index的位置，如果index比size的一半(size >> 1,右移运算，相当于除以2)要小，就从头开始遍历。否则，从尾部开始遍历。从而可以知道，对于LinkedList来说，操作的元素的位置越往中间靠拢，效率就越低
Node<E> node(int index) {// assert isElementIndex(index);
if (index < (size >> 1)) { Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x; } else { Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x; } }这个函数的工作就只是负责把元素插入到相应的位置而已，关键的工作在node()方法中已经完成了
void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode;if (pred == null) first = newNode;else pred.next = newNode; size++; modCount++; }总结
# ArrayList、LinkedList查找
这就没啥好说的了，对于ArrayList，无论什么位置，都是直接通过索引定位到元素，时间复杂度O(1)
而对于LinkedList查找，其核心方法就是上面所说的node()方法，所以头尾查找速度极快，越往中间靠拢效率越低
---END---
微信终于可以发送大文件了！
更文不易，点个“在看”支持一下👇