上篇文章和一块学习了ArrayList源码，本文再和大家一块学习一下LinkedList源码。
LinkedList底层是基于双链表，实现了List和Deque接口，所以既有List增删查改的功能，又有Deque的头尾操作的功能，在队列源码中杯经常使用。
先看一下LinkedList的常用方法。
1. 用法
1.1 常见的增删查改
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("a"); // 添加元素
linkedList.remove("a"); // 删除元素
String key = linkedList.get(0); // 通过下标查询元素
String oldKey = linkedList.set(0, "b"); // 通过下标修改元素1.2 从头尾添加
// 从头部添加
linkedList.offerFirst("a");
linkedList.addFirst("a");
linkedList.push("a");
// 从尾部添加
linkedList.add("a");
linkedList.offer("a");
linkedList.offerLast("a");
linkedList.addLast("a");1.3 从头尾删除
// 从头部删除
boolean succss = linkedList.remove("a");
String first = linkedList.removeFirst();
boolean success = linkedList.removeFirstOccurrence("a");
String first = linkedList.poll();
String first = linkedList.pollFirst();
String pop = linkedList.pop();
// 从尾部删除
String last = linkedList.removeLast();
boolean success = linkedList.removeLastOccurrence("a");
String last = linkedList.pollLast();统计到表格中看一下，先看添加：
方法含义 | 返回布尔值 | 不返回 |
从头部添加 | offerFirst | addFirst/push |
从尾部添加 | add/offer/offerLast | addLast |
删除的方法：
方法含义 | 返回布尔值 | 返回旧值 | 实现原理 |
从头部删除 | remove/removeFirstOccurrence | poll/pollFirst removeFirst/pop | removeFirst/pop如果不存在则抛异常 |
从尾部删除 | removeLastOccurrence | pollLast/removeLast | removeLast如果不存在则抛异常 |
查找的方法：
方法含义 | 如果不存在则返回null | 如果不存在则抛异常 |
从头部查找 | peek/peekFirst | get/getFirst/element |
从尾部查找 | peekLast | getLast |
2. 实现原理
LinkedList底层是基于双链表实现的，非线程安全。
双链表的节点就是：
private static class Node<E> {
E item; // 节点值
Node<E> next; // 下一个节点
Node<E> prev; // 前一个节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}3. 添加
// 添加元素e
public boolean add(E e) {
// 直接追加到末尾
linkLast(e);
return true;
}
// 从尾部开始追加节点
void linkLast(E e) {
// 暂存尾节点
final Node<E> l = last;
// 新建节点，l是新节点的上一个节点，e是新节点的值，null是新节点的下一个节点
final Node<E> newNode = new Node<>(l, e, null);
// 把新节点赋值给尾节点
last = newNode;
//如果原尾节点是null，代表链表为空，把新节点也赋值给头结点
if (l == null)
first = newNode;
else
// 新节点变成原尾节点的下一个节点
l.next = newNode;
size++;
modCount++;
}4. 删除
// 按值大小删除
public boolean remove(Object o) {
// 如果值是null，就遍历链表。如果链表的节点值也是null，就删除该节点
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 如果值不是null，就遍历链表，跟链表节点值比较，如果相等，就删除该节点
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}再看一下按下标删除的源码：
// 按下标删除
public E remove(int index) {
// 校验下标是否越界
if (!(index >= 0 && index < size)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
return unlink(node(index));
}
// 获取该下标的节点
Node<E> node(int 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;
}
}再看一下核心的删除节点的方法unlink()
// 删除x节点
E unlink(Node<E> x) {
// 暂存当前节点值、下一个节点和上一个节点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果上一个节点是null，表示要删除的节点是头结点，下一个节点就变成头结点
if (prev == null) {
first = next;
} else {
// 否则，就断开和上一个节点的连接
prev.next = next;
x.prev = null;
}
// 如果下一个节点是null，表示要删除的节点是尾节点，上一个节点就变成尾节点
if (next == null) {
last = prev;
} else {
// 否则，就断开和下一个节点的连接
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}5. 查找
// 根据下标查找
public E get(int index) {
// 校验下标是否越界
if (!(index >= 0 && index < size)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// node方法业务逻辑刚讲过。如果下标是链表的前半部分，就从头开始查找，否则从尾部开始查找
return node(index).item;
}6. 总结
- LinkedList底层基于双链表，元素是链式存储的，不需要扩容，没有空间大小限制，可以无限添加。
- 可以在头尾节点进行添加删除，时间复杂度是O(1)，适合做延迟队列，一端添加，一端删除。
- 允许元素是null，非线程安全。
7. ArrayList跟LinkedList区别
7.1 查找的区别
- ArrayList底层是数组，通过下标顺序存储，适合查找较多的场景，时间复杂度是O(1)
- LinkedList底层是双链表，链式存储，查找的时候需要遍历整个链表，时间复杂度是O(n)
7.2 添加删除的区别
- ArrayList每次添加删除的时候，都需要数组拷贝，必要时还需要扩容，再次拷贝，比较耗时。
- LinkedList添加删除的时候，只涉及的相邻的前后节点，不需要扩容，效率更高。
关注我，分享更多技术源码干货。