本文介绍 Java 集合框架中的 LinkedList 类及其底层双向链表数据结构。涵盖 LinkedList 实现的接口（List、Deque 等）、核心特性（增删效率高、随机访问低效）、手动实现单链表的关键代码逻辑（头插尾插、查找删除），以及官方 API 的使用和遍历方式（迭代器、增强 for）。旨在帮助读者理解链表原理及在 Java 中的应用。
本文分享链表与 LinkedList 的内容。结构类似，若有顺序表基础会更容易理解。我们从集合框架出发。
这是 LinkedList 作为列表的核心接口，它继承自 Collection 接口，定义了有序集合的基础行为。
get(int index)、set(int index, E element)；
支持增删改查的全量列表操作，例如 add(E e)、remove(int index)、contains(Object o) 等。这是 LinkedList 区别于 ArrayList 的关键接口，它继承自 Queue 接口（Queue 又继承自 Collection），是双端队列的核心接口。
offer(E e)（队尾入队）、poll()（队首出队）；
双端操作：支持队首 / 队尾双向操作，如 addFirst(E e)（队首添加）、addLast(E e)（队尾添加）、getFirst()（获取队首）、getLast()（获取队尾）；
栈行为：遵循后进先出（LIFO），可通过 push(E e)（等效于 addFirst，入栈）、pop()（等效于 removeFirst，出栈）实现栈功能。一般的链表分为有头无头结点、单项双向、有无尾结点，不过大差不差。我们手动实现的为无头结点单项的链表。
熟悉了这个，其他类型的也就水到渠成！
static class ListNode {
public int val;
public ListNode next;
// 构造方法实例化节点
public ListNode(int val) {
this.val = val;
}
}
// 定义 listNode 的头结点
public ListNode head;
public ListNode createList() {
ListNode node0 = new ListNode(11);
ListNode node1 = new ListNode(11);
ListNode node2 = new ListNode(11);
ListNode node3 = new ListNode(11);
ListNode node4 = new ListNode(11);
node0.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
head = node0;
return head;
}
// 头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
// 尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
// 链表为空直接插入
if (head == null) {
head = node;
return;
}
// 找到最后一个
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
// 任意位置插入，第一个数据节点为 0 号下标
public void addIndex(int index, int data) {
// 检查 index
if (index < 0 || index > size()) {
System.out.println("index 不合法");
}
// 头插入
if (index == 1) {
addLast(data);
}
// 尾插入
if (index == size()) {
addLast(data);
}
// 中间插入
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
public ListNode findIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}
// 查找是否包含关键字 key 是否在单链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
// 删除第一次出现关键字为 key 的节点
public void remove(int key) {
// 空链表情况
if (head == null) {
System.out.println("空链表异常");
return;
}
// 删除第一个元素
if (head.val == key) {
head = head.next;
return;
}
// 处理中间部分
// 找到 del 之前的 ret
ListNode ret = search(key);
if (ret == null) {
System.out.println("没有要删除元素");
return;
}
ListNode del = ret.next;
ret.next = del.next;
}
public ListNode search(int val) {
ListNode cur = head;
while (cur.next != null) {
if (cur.next.val == val) {
return cur;
}
cur = cur.next;
}
return null;
}
// 删除所有值为 key 的节点
public void removeAllKey(int key) {
// 第一空链表情况
if (head == null) {
System.out.println("空链表异常");
}
ListNode prev = head;
ListNode cur = head.next;
// 处理中间部分
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
} else {
prev = cur;
cur = cur.next;
}
cur = cur.next;
}
// 最后处理头节点
if (head.val == key) {
head = head.next;
}
}
// 得到单链表的长度
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode crn = cur.next;
// 在删除节点之前保存之后的节点
// cur.val = null; // 引用类型处理方法
cur.next = crn;
cur = null;
cur = crn;
}
head = null;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
我们看一下 java 官方包中的方法。
就是两个简单的构造方法。
public LinkedList() {}
无参构造器的实现非常简洁，仅初始化一个空的双向链表： 链表的 头指针（first）和尾指针（last） 默认都为 null； 链表的元素个数（size）初始化为 0； 没有预先分配任何节点或内存，链表处于完全空的状态。
public LinkedList(Collection<? extends E> c) {
this(); // 先调用无参构造器初始化空链表
addAll(c); // 将集合 c 中的元素批量添加到链表中
}
List<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new ArrayList<>();
// 使用 ArrayList 构建 LinkedList
LinkedList<Integer> list3 = new LinkedList<>(list2);
// List 实现了 Collection Integer 是 Integer 或者子类
需要注意的就是每个方法的返回类型 + 方法名 + 形参。 一定要动手操作一下。
System.out.println(list);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println(" ");
for (Integer x : list) {
System.out.print(x + " ");
}
在 Java 集合框架中，迭代器（Iterator） 是用于遍历集合元素的统一接口，它提供了一种不依赖集合底层结构的遍历方式，核心作用是'解耦集合与遍历逻辑'。
// 迭代器
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println(" ");
ListIterator<Integer> iterator1 = list.listIterator(list.size());
while (iterator1.hasPrevious()) {
System.out.print(iterator1.previous() + " ");
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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