图解LinkedList底层原理
本篇将讲解Java中的一个集合LinkedList的底层实现原理，会查看并分析底层源码，结合图解的方式，理解其添加数据的过程
数据结构
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;}
}
- 每个节点存储当前元素的值（
item）及指向前后节点的引用（prev和next） LinkedList是一个双向链表，支持从头部或尾部高效地插入和删除
成员变量
LinkedList 的核心成员变量如下：
transient int size = 0; // 链表中元素的数量
transient Node<E> first; // 链表的头节点
transient Node<E> last; // 链表的尾节点
size：记录链表中元素的数量first：指向链表的头节点last：指向链表的尾节点
构造方法
LinkedList 提供了默认的无参构造方法：
public LinkedList() {}
LinkedList初始化时，first和last都为null，表示链表为空。
add 方法源码分析
当我们调用 add(E e) 方法时，例如：
LinkedList<String> list = new LinkedList<>();
list.add("Hello");
以下是 add 方法的源码：
public boolean add(E e) {linkLast(e);return true;
}
add方法通过调用linkLast(E e)方法，将新元素添加到链表尾部
linkLast 方法解析
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; // 新节点即为头节点elsel.next = newNode; // 更新旧尾节点的 next 引用size++; // 链表长度加 1modCount++; // 修改计数器
}
当我add第一个元素e时，他的插入过程如下：
-
新节点创建：
final Node<E> l = last; // 获取当前尾节点 final Node<E> newNode = new Node<>(l, e, null) last = newNode; // 更新尾节点通过
Node构造方法，将新节点的prev指向当前尾节点，当前尾节点为null，所以prev指向null，next指向null，再将尾节点last指向新节点 -
更新链表结构：
if (l == null) // 如果链表为空first = newNode; // 新节点即为头节点elsel.next = newNode;- 如果链表为空（
l == null），更新头节点first - 如果链表非空，将当前尾节点的
next指向新节点
此时的
l是未更新之前的last，为null，所以更新头节点也指向Node 1 - 如果链表为空（
-
更新尾节点和链表长度：新节点成为尾节点，
size自增
接着我们再add第二个元素e2，同样的步骤再次执行：
-
新节点创建：
final Node<E> l = last; // 获取当前尾节点 final Node<E> newNode = new Node<>(l, e, null) last = newNode; // 更新尾节点在添加第一个元素时，尾节点更新为了Node 1，此时的把尾节点赋值给
l，l的值为Node 1创建一个新节点传入了
l因此新节点的prev指向Node 1，next为null,并且更新尾节点，把尾节点指向新节点，此时last的值就为Node 2了 -
更新链表结构:
if (l == null) // 如果链表为空first = newNode; // 新节点即为头节点elsel.next = newNode;此时的
l早已不是null了，而是Node1，因此走else的逻辑，将l， 也就是Node 1的next指向新节点，形成一个双向指针 -
更新尾节点和链表长度：新节点成为尾节点，
size自增
此时双向链表的雏形已经形成
接着我们再次add一个新元素e3，依旧是同样的操作：
-
新节点创建：
final Node<E> l = last; // 获取当前尾节点 final Node<E> newNode = new Node<>(l, e, null) last = newNode; // 更新尾节点经过e2的插入过程，
last此时为Node2，创建新节点时，其prev就为Node2，last也更新为了Node3 -
更新链表结构:
if (l == null) // 如果链表为空first = newNode; // 新节点即为头节点elsel.next = newNode;依旧执行else，将Node 2 的
next指向Node 3，形成双向链表：
linkBefore 方法
void linkBefore(E e, Node<E> succ) {final Node<E> pred = succ.prev; // 获取前驱节点final Node<E> newNode = new Node<>(pred, e, succ); // 创建新节点succ.prev = newNode; // 更新后继节点的 previf (pred == null) // 如果插入位置为头部first = newNode;elsepred.next = newNode; // 更新前驱节点的 nextsize++;modCount++;
}
该方法与尾插法类似，节点的插入位置变成了从头节点位置插入
具体流程:
- 确定插入位置的前驱和后继节点
- 更新新节点的
prev和next引用，同时修改前驱和后继节点的指针 - 如果插入位置为链表头部或尾部，更新
first或last节点
插入到指定位置
add(int index, E element)
add 方法支持在链表的任意位置插入元素：
public void add(int index, E element) {checkPositionIndex(index); // 检查索引范围if (index == size) // 如果插入到链表尾部linkLast(element);elselinkBefore(element, node(index));
}
关键逻辑
- 边界判断：通过
checkPositionIndex()检查索引是否越界 - 插入方式：
- 如果插入位置为链表尾部，调用
linkLast方法 - 如果插入位置在中间，调用
linkBefore方法
- 如果插入位置为链表尾部，调用