本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
点击上方“Java知音”，选择“置顶公众号”
技术文章第一时间送达！
作者：你在我家门口
juejin.im/post/5c00987de51d451aa843b67bjuejin.im/post/5c00987de51d451aa843b67b
测试结果
废话不多说，先上测试结果。作者分别在ArrayList和LinkedList的头部、尾部和中间三个位置插入与查找100000个元素所消耗的时间来进行对比测试，下面是测试结果
在这里说明一下测试的环境，尾部插入是在空表的基础上测试的，头部和中间位置插入是在已存在100000个元素的表上进行测试的
测试结论
ArrayList除了尾部插入的性能较好外（位置越靠后性能越好），其他位置性能就不如人意了
源码分析
我们把Java中的ArrayList和LinkedList就是分别对顺序表和双向链表的一种实现，所以在进行源码分析之前，我们先来简单回顾一下数据结构中的顺序表与双向链表中的关键概念
双向链表：不需要申请连续的内存空间保存元素，需要通过元素的头尾指针找到前继与后继元素（查找元素的时候需要从头or尾开始遍历整个链表，直到找到目标元素）。在双向链表中插入or删除元素不需要移动元素，只需要改变相关元素的头尾指针即可。
所以我们潜意识会认为：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个元素耗时：11387ms
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 NodeE first;
/**
* Pointer to last node.
*/
transient NodeE 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 NodeE l = last;
// 创建一个新的结点，其头结点指向last
final NodeE 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来说，操作的元素的位置越往中间靠拢，效率就越低
NodeE node(int index) {
// assert isElementIndex(index);
if (index (size 1)) {
NodeE x = first;
for (int i = 0; i index; i++)
x = x.next;
return x;
} else {
NodeE x = last;
for (int i = size - 1; i index; i--)
x = x.prev;
return x;
}
}
这个函数的工作就只是负责把元素插入到相应的位置而已，关键的工作在node()方法中已经完成了
void linkBefore(E e, NodeE succ) {
// assert succ != null;
final NodeE pred = succ.prev;
final NodeE newNode = new Node(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
总结
但是对于ArrayList来说，头部的每一次插入都需要移动size-1个元素，效率可想而知
ArrayList、LinkedList查找
而对于LinkedList查找，其核心方法就是上面所说的node()方法，所以头尾查找速度极快，越往中间靠拢效率越低
推荐阅读(点击即可跳转阅读)
2.面试题内容聚合
3.设计模式内容聚合
5.多线程内容聚合
觉得不错？欢迎转发分享给更多人
我知道你 “在看”
原文始发于微信公众号（Java知音）：LinkedList真的是查找慢增删快？
