Javajava算法
Java 双向链表实现与 LinkedList 源码解析
本文详细讲解了 Java 中双向链表的数据结构原理及模拟实现，包括节点设计、头插尾插、指定位置插入删除等操作。随后深入分析了 JDK 中 LinkedList 类的底层机制、构造方法及常用 API。最后对比了 ArrayList 与 LinkedList 在存储结构、访问效率及应用场景上的差异，帮助开发者根据实际需求选择合适的数据结构。
本文详细讲解了 Java 中双向链表的数据结构原理及模拟实现，包括节点设计、头插尾插、指定位置插入删除等操作。随后深入分析了 JDK 中 LinkedList 类的底层机制、构造方法及常用 API。最后对比了 ArrayList 与 LinkedList 在存储结构、访问效率及应用场景上的差异，帮助开发者根据实际需求选择合适的数据结构。
双向链表与单向链表相比，多了一个前驱 prev，解决了单向链表很多缺点：单向链表的每个节点仅存储后继节点地址，这导致其在实际应用中存在明显局限：
遍历方向单一：只能从表头（head）向表尾（tail）遍历，无法反向查找。 删除操作低效：若要删除指定节点，需先从头遍历找到其前驱节点，时间复杂度为 O(n)。 表尾操作不便：无法直接获取表尾节点的前驱，若需在表尾插入后修改前驱指针，需重新遍历。
双向链表通过在节点中增加前驱节点地址域，解决了以上问题，所以在实际开发中，使用更多的是双向链表。
val 数据，next 后继，prev 前驱，双向链表的前驱节点，可以找到前一个节点，为了方便从后往前遍历，我们使用 last 标记最后一个节点。
static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
先创建一个新节点 node，如果链表为空，head 和 last 都指向新节点，当链表不为空时，让新节点的 next 指向头节点（先绑定后面），然后将头节点的前驱 prev 赋值为新节点的地址，最后让 head 指向新的节点。
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
跟头插法一样，创建一个节点，判断链表是否为空，为空就让 head 和 last 都指向新节点，当链表不为空时，让最后一个节点的 next 指向新的节点（先绑定），然后让新节点的前驱指向前一个节点的地址，最后让 last 指向新节点。
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}
双向链表可以找到前一个节点，所以可以让 cur 直接走到想要插入的位置，先判断位置是否合法，然后开始插入，先绑定后面让新节点的 next 指向 cur 节点的地址，然后让前一个节点的 next 指向新的节点的地址，在将新节点的前驱改为 cur 的前驱，cur 的前驱改为新节点。
public void addIndex(int index, int data) {
// 检查 index 的合法性
checkIndex(index);
// 特殊位置处理
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
// 指定插入
ListNode cur = searchIndex(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
// 寻找位置
private ListNode searchIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
// 自定义异常
private void checkIndex(int index) {
if (index < 0 || index > size()) {
throw new IllegalArgumentException("index 位置不合法：" + index);
}
}
先遍历，找到所要删除的那个节点，当 cur 走到要删除的节点时，常规操作：cur.next.prev = cur.prev; cur.prev.next = cur.next;但还有其他情况：比如要删除的是头节点或者尾节点，只要一个节点的情况，具体操作看下面的代码详解。
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
// 开始删除
if (cur == head) {
// 删除的时头节点
head = head.next;
// 如果只有一个节点，head 为空，它的前驱就会空指针异常，所以判断一下
if (head != null) {
head.prev = null;
}
} else {
// 不是头节点
if (cur == last) {
// 删除的是尾节点
cur.prev.next = cur.next;
last = last.prev;
} else {
// 正常情况：中间节点
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
}
return;
}
cur = cur.next;
}
}
只要将上面的代码中 return 去掉，就能删除所有值为 key 的节点，删完一个后不返回，继续遍历，直到全部删除。
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
// 开始删除
if (cur == head) {
// 删除的时头节点
head = head.next;
// 如果只有一个节点，head 为空，它的前驱就会空指针异常，所以判断一下
if (head != null) {
head.prev = null;
}
} else {
// 不是头节点
if (cur == last) {
// 删除的是尾节点
cur.prev.next = cur.next;
last = last.prev;
} else {
// 正常情况：中间节点
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
}
}
cur = cur.next;
}
}
【方法一：】直接将头和尾置空
public void clear() {
head = last = null;
}
【方法二：】将一个一个的节点置空
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
cur.prev = null;
cur.next = null;
cur = curN;
}
head = null;
last = null;
}
LinkedList 使用双向链表结构，实现了 List 接口。在任意位置插入和删除元素时效率较高，时间复杂度为 O(1)。
| 方法签名 | 描述 |
|---|---|
LinkedList() | 无参构造方法，创建一个空链表。 |
public LinkedList(Collection<? extends E> c) | 使用其他集合容器中的元素构造 List |
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
List<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new ArrayList<>();
list.add(1); // 默认尾插
list.add(11);
list.add(12);
list.add(13);
System.out.println(list);
}
| 方法 | 解释 |
|---|---|
boolean add(E e) | 在列表尾部插入元素 e |
void add(int index, E element) | 将元素 e 插入到指定 index 位置 |
boolean addAll(Collection<? extends E> c) | 将集合 c 中所有元素插入到列表尾部 |
E remove(int index) | 删除并返回 index 位置的元素 |
boolean remove(Object o) | 删除列表中首次遇到的指定对象 o |
E get(int index) | 获取 index 位置的元素 |
E set(int index, E element) | 将 index 位置的元素替换为 element 并返回旧值 |
void clear() | 清空列表中的所有元素 |
boolean contains(Object o) | 判断列表中是否包含对象 o |
int indexOf(Object o) | 返回第一个 o 对象的下标，未找到返回 -1 |
int lastIndexOf(Object o) | 返回最后一个 o 对象的下标，未找到返回 -1 |
List<E> subList(int fromIndex, int toIndex) | 截取从 fromIndex 到 toIndex 的子列表 |
System.out.println(list);
for (Integer x : list) {
System.out.println(x + " ");
}
// 迭代器遍历
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
System.out.println(it.next() + " ");
}
// 迭代器遍历：专门遍历 List
ListIterator<Integer> listIterator = list.listIterator();
// 可以给参数，从 index 开始打印
while (listIterator.hasNext()) {
System.out.println(listIterator.next() + " ");
}
// 反向迭代器
ListIterator<Integer> listIterator1 = list.listIterator();
// 可以给参数，从 index 开始打印
while (listIterator.hasPrevious()) {
System.out.println(listIterator.next() + " ");
}
| 不同点 | ArrayList | LinkedList |
|---|---|---|
| 存储空间 | 物理上连续 | 逻辑上连续，物理上不连续 |
| 随机访问 | 支持 O(1) 时间复杂度 | 不支持，需遍历 O(N) 时间复杂度 |
| 头插操作 | 需搬移元素，效率低 O(N) | 修改引用指向，效率高 O(1) |
| 插入扩容 | 空间不足时需扩容 | 无容量概念，动态增加节点 |
| 应用场景 | 元素高效存储 + 频繁随机访问 | 频繁在任意位置插入/删除 |
本文围绕双向链表和 LinkedList 展开了系统讲解。
双向链表凭借'每个节点保存前驱和后继引用'的结构，在插入、删除操作上有着 O(1) 的时间复杂度优势。LinkedList 作为双向链表的 Java 实现，不仅提供了如 addFirst、removeLast 等丰富方法，支持迭代器、增强 for 等多种遍历方式，还能充当队列、栈使用。和 ArrayList 相比，LinkedList 适合频繁进行插入删除的场景，ArrayList 则更适合元素存储和随机访问的场景。掌握这些知识，能让你在面对不同业务场景时，合理选择数据结构，写出高效且易维护的代码。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online