LinkedList 深度解析：核心原理与实践
LinkedList 深度面试指南：核心原理与实践
一、底层数据结构与特性
1. 核心数据结构
// JDK 17 源码片段
private static class Node<E> {E item; // 存储的数据元素Node<E> next; // 指向下一个节点Node<E> prev; // 指向前一个节点
}transient Node<E> first; // 链表头节点
transient Node<E> last; // 链表尾节点
transient int size = 0; // 元素数量
2. 关键特性
| 特性 | 说明 |
|---|---|
| 双向链表结构 | 每个节点包含前后指针，支持双向遍历 |
| 非连续内存存储 | 元素存储在离散的节点中，不需要扩容 |
| 非线程安全 | 多线程环境下需要外部同步 |
| 允许 null 值 | 可以存储任意数量的 null |
| 实现多个接口 | 实现了 List、Deque 接口，可作列表、双端队列、栈使用 |
| Fail-Fast 迭代器 | 迭代过程中检测到结构性修改会抛出 ConcurrentModificationException |
二、核心操作机制解析
1. 添加元素机制
头部添加：
public void addFirst(E e) {linkFirst(e);
}// 将元素e作为新的头节点插入到链表的最前面
private void linkFirst(E e) {// 保存当前第一个节点的引用ffinal Node<E> f = first;// 创建新节点newNode，其前驱为null，后继指向原第一个节点ffinal Node<E> newNode = new Node<>(null, e, f);// 将first指针指向新节点first = newNode;if (f == null)// last也指向新节点last = newNode;else// 否则将原第一个节点的prev指向新节点f.prev = newNode;// 链表大小加1，修改计数器加1size++;modCount++;
}
尾部添加：
public boolean add(E e) {linkLast(e);return true;
}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;size++;modCount++;
}
2. 删除元素机制
public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}E unlink(Node<E> x) {final E element = x.item