从源码上分析 LinkedList（附图）
从源码上分析 LinkedList（附图）
前言
上一篇我们介绍了 ArrayList，这次，我们再看看一下它的兄弟：LinkedList 。
LinkedList 同样也实现了 List 接口，底层原理是双向链表，那么它又是如何实现的呢？继续来看吧。
源码分析
成员变量
LinkedList 只有三个成员变量：
transientint size = 0;
transient Node<E> first;
transient Node<E> last;
size 属性不用说，肯定是表示链表的逻辑长度，first 应该是链表的第一个元素，last 表示最后一个元素。
构造方法
先来看无参构造：
public LinkedList() {
}无参构造没有任何逻辑，那么再来看看其他的构造方法：
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}这里牵扯到要给 addAll 方法，一会在常用方法里我们会讲到，这里先放一放。
这次我们带上内存图来分析，会更直观一些，首先用无参构造来创建一个对象：
1 | List<Student> list = new LinkedList<>(); |
|---|
注：为了节省篇幅，本图省略了一些细节上东西，如常量池，方法区等内容。
常用方法
add
首先是 add 方法：
public boolean add(E e) {
linkLast(e);
return true;
}void linkLast(E e) {
final Node<E> l = last; // last 节点表示添加前最后一个节点
final Node<E> newNode = new Node<>(l, e, null); // 要添加的节点的上一个节点应该是 last 节点。
last = newNode; // 添加了节点后，添加的新节点应该为 last 节点。
if (l == null) // 如果当前元素没有上一个元素，则表示为第一次添加，
first = newNode; // 那么当前节点应该也算是 first 节点。
else
l.next = newNode;
size++; // 逻辑长度 + 1
modCount++; // 修改次数 + 1
}这里提到了 Node 类，来看看它的定义：
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;
}
}原来 Node 类是 LinkedList 的静态内部类，表示链表的一个节点。
那么当我们执行这段代码后，会发送什么呢？
1 | list.add(new Student("张三", 20)); |
|---|
那我们再添加一个元素呢?
1 | list.add(new Student("李四", 21)); |
|---|
可能看起来有写复杂，其实也不难理解，耐下心对照源码好好看一下，应该就能理解这张图的意思了。
我们再添加两个元素看看效果。
list.add(new Student("王五", 22));
list.add(new Student("赵六", 23));
remove
添加了这么多，我们删除一个试试，先来看看源码：
// 根据索引删除
public E remove(int index) {
checkElementIndex(index); // 检查要删除的元素索引是否有效，即 0 <= index < size
return unlink(node(index)); // node(index) 方法找到第 index 个元素
}private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; // 要删除节点的值
final Node<E> next = x.next; // 当删除节点的后继节点
final Node<E> prev = x.prev; // 要删除元素的前驱结点
if (prev == null) { // 如果没有前驱节点，表示为头节点
first = next; // 删除头节点后，更换 first 指向
} else { // 如果不是头节点
prev.next = next; // 将前驱节点的 next 指向要删除节点的后继节点
x.prev = null; // 将要删除的节点不再指向任何节点
}
if (next == null) { // 如果当前节点为最后一个节点
last = prev; // 将 last 指向倒数第二个
} else { // 如果不是最后一个节点
next.prev = prev; // 将后继节点的 prev 指向要删除元素的前驱节点
x.next = null; // 将要删除的节点不再指向任何节点
}
x.item = null; // 将要删除的元素的数据清空
size--; // 逻辑长度 - 1
modCount++; // 修改次数 + 1
return element;
}可能这里的这 10 和 17 行不太容易理解：
prev.next = next; // 将前驱节点的 next 指向要删除节点的后继节点
next.prev = prev; // 将后继节点的 prev 指向要删除元素的前驱节点
举个简单的例子: 张三 <==> 李四 <==> 王五
那么要删除李四的话，应该要将张三的 “下一个” 指向王五吧，也就是 prev.next = next;。同样，应为是双向链表，所以也应该让王五的 “上一个” 指向张三，即 next.prev = prev;。
这里讲解的是根据索引删除，还有根据元素删除，其实原理是一样的，主要是 unlink 这个方法，先根据传入的参数，找到要删除的元素，然后进行 unlink 方法的逻辑即可，这里就不再展开，如果你看懂了根据索引删除，相信你也能理解根据元素删除。
但是需要注意的是：如果删除的是引用数据类型的话，需要重写 equals 方法，不然可能会无法进行删除操作哦。
其实仔细想想也能理解，既然需要 找到要删除的元素，那么如何判断传入的参数和要删除的是同一个呢？只有 equals 方法了，而默认从 Object 继承的 equals 方法可不一定能满足我们的需求，因为它只比较地址值，所以我们需要重写 equals 方法。
get
public E get(int index) {
checkElementIndex(index); // 检查要获取的元素索引是否有效，即 0 <= index < size
return node(index).item; // 根据索引来找到这个元素，返回它的 item 值
}Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // 如果要删除的元素在前半段, 则从 first 开始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 如果要删除的元素在后半段, 则从 last 开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}这里用了一个很巧妙的小算法，既然我们知道链表的长度，那么当要删除的元素 索引 < 长度 / 2，就从第一个开始找，反之从最后一个开始找，长度 / 2 可以改写为位运算即：size >> 1，效率更高一些。
先讲这么多，如果你看懂了这些，相信 LinkedList 的其他方法，你也能够轻松的理解。
总结
根据上方的源码分析，我们可以总结出 LinkedList 的一些特性：
LinkedList底层数据结构是双向链表。- 不能对元素进行随机访问，虽然提供了 get 方法，但这个方法是通过遍历来实现的。
- 删除、添加元素的效率很高，但查找元素的的效率较差。
腾讯云开发者
