一、单向链表的模拟实现
单向链表的每个节点只包含自身数据和下一个节点的引用，只能从头节点向尾节点遍历，操作相对简单，是理解链表结构的基础。
完整实现代码
public class MySinglyLinkedList { // 重命名类，明确是单向链表，更易理解
// 静态内部类：链表节点（封装数据和下一个节点引用）
// 为什么用静态内部类？避免外部类的隐式引用，节省内存，且节点逻辑与外部链表独立
static class ListNode {
public int val; // 节点存储的数据
public ListNode next; // 指向下一个节点的引用（原代码中Address命名不直观，改为next更符合行业惯例）
// 构造方法：初始化节点数据
public ListNode(int val) {
this.val = val;
// next 默认为 null，无需显式赋值
}
}
public ListNode head; // 链表的头节点（链表的入口，通过它遍历整个链表）
/**
* 手动创建一个测试链表（用于快速验证功能，非核心方法）
*/
public void createLinkedList() {
ListNode node1 = new ListNode(12);
ListNode node2 = new ListNode(23);
ListNode node3 = new ListNode(34);
ListNode node4 = new ListNode(45);
ListNode node5 = new ListNode(56);
// 建立节点间的引用关系，形成链表
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1; // 头节点指向第一个节点
}
/**
* 头插法：在链表头部插入新节点
* 优势：时间复杂度 O(1)，无需遍历链表
* @param data 要插入的数据
*/
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
// 新节点的 next 指向原来的头节点
newNode.next = head;
// 头节点更新为新节点
head = newNode;
}
/**
* 尾插法：在链表尾部插入新节点
* 劣势：时间复杂度 O(n)，需要遍历到链表末尾
* @param data 要插入的数据
*/
public void addLast(int data) {
ListNode newNode = new ListNode(data);
// 特殊情况：链表为空，直接将头节点指向新节点
if (head == null) {
head = newNode;
return;
}
// 遍历到链表末尾（cur.next 为 null 时，cur 就是尾节点）
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
// 尾节点的 next 指向新节点
cur.next = newNode;
}
/**
* 任意位置插入：在下标 index 处插入新节点（下标从 0 开始）
* @param index 插入位置
* @param data 插入数据
*/
public void addIndex(int index, int data) {
int size = size();
// 1. 合法性校验：index 小于 0 或大于链表长度，插入失败
if (index < 0 || index > size) {
System.out.println("插入下标不合法！");
return;
}
// 2. 复用头插法：index 为 0，直接头部插入
if (index == 0) {
addFirst(data);
return;
}
// 3. 复用尾插法：index 等于链表长度，直接尾部插入
if (index == size) {
addLast(data);
return;
}
// 4. 中间插入：找到 index 前一个节点（cur）
ListNode newNode = new ListNode(data);
ListNode cur = head;
int count = 0;
while (count != index - 1) { // 优化原代码，直接找到前驱节点，更高效
cur = cur.next;
count++;
}
// 5. 建立引用关系（先绑后面，再绑前面，避免链表断裂）
newNode.next = cur.next;
cur.next = newNode;
}
/**
* 查找是否包含关键字 key
* @param key 要查找的关键字
* @return 包含返回 true，否则返回 false
*/
public boolean contains(int key) {
ListNode cur = head;
// 遍历整个链表，逐一比对数据
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next; // 原代码遗漏此句，会导致死循环，已修复
}
return false;
}
/**
* 删除第一次出现关键字为 key 的节点
* @param key 要删除的关键字
*/
public void remove(int key) {
// 特殊情况1：链表为空，直接返回
if (head == null) {
System.out.println("链表为空，无法删除！");
return;
}
// 特殊情况2：头节点就是要删除的节点
if (head.val == key) {
head = head.next;
return;
}
// 1. 找到要删除节点的前驱节点（cur）
ListNode cur = head;
while (cur.next != null) {
if (cur.next.val == key) {
break; // 找到前驱节点，跳出循环
}
cur = cur.next;
}
// 2. 判断是否找到（避免链表中无 key 的情况）
if (cur.next != null) {
// 3. 跳过要删除的节点，建立新的引用
cur.next = cur.next.next;
} else {
System.out.println("链表中无此关键字，无法删除！");
}
}
/**
* 删除所有值为 key 的节点
* @param key 要删除的关键字
*/
public void removeAllKey(int key) {
// 特殊情况：链表为空，直接返回
if (head == null) {
System.out.println("链表为空，无法删除！");
return;
}
// 1. 处理中间和尾部节点（借助前驱节点 prev 和当前节点 cur）
ListNode prev = head;
ListNode cur = head.next;
while (cur != null) {
if (cur.val == key) {
// 找到要删除的节点，前驱节点直接跳过当前节点
prev.next = cur.next;
} else {
// 未找到，前驱节点和当前节点同时后移
prev = cur;
}
// 无论是否删除，当前节点都要后移
cur = cur.next;
}
// 2. 处理头节点（最后处理，避免链表断裂）
if (head.val == key) {
head = head.next;
}
}
/**
* 得到链表的长度
* @return 链表节点个数
*/
public int size() {
ListNode cur = head;
int count = 0;
// 遍历链表，统计节点个数
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
/**
* 清空链表
* 简单高效：直接将头节点置为 null，GC 会自动回收链表节点
*/
public void clear() {
head = null;
}
/**
* 打印链表所有数据
*/
public void display() {
ListNode cur = head;
// 遍历链表，逐个打印节点数据
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println(); // 换行，优化打印格式
}
}
二、双向链表的模拟实现
双向链表的每个节点包含自身数据、上一个节点引用（prev）和下一个节点引用（next），可以双向遍历，首尾操作更高效，也是 Java LinkedList 的底层实现。
完整实现代码
public class MyDoublyLinkedList { // 重命名类，明确是双向链表
// 静态内部类：双向链表节点（封装数据、前驱节点、后继节点）
static class ListNode {
public int val; // 节点存储的数据
public ListNode prev; // 指向前一个节点的引用
public ListNode next; // 指向后一个节点的引用
// 构造方法：初始化节点数据
public ListNode(int val) {
this.val = val;
// prev 和 next 默认为 null，无需显式赋值
}
}
public ListNode head; // 链表头节点
public ListNode last; // 链表尾节点（双向链表特有，直接指向尾节点，尾插法时间复杂度 O(1)）
/**
* 头插法：在链表头部插入新节点
* @param data 要插入的数据
*/
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
// 特殊情况：链表为空，头节点和尾节点都指向新节点
if (head == null) {
head = newNode;
last = newNode;
return;
}
// 1. 新节点的 next 指向原来的头节点
newNode.next = head;
// 2. 原来的头节点的 prev 指向新节点
head.prev = newNode;
// 3. 头节点更新为新节点
head = newNode;
}
/**
* 尾插法：在链表尾部插入新节点
* 优势：借助 last 节点，时间复杂度 O(1)
* @param data 要插入的数据
*/
public void addLast(int data) {
ListNode newNode = new ListNode(data);
// 特殊情况：链表为空，头节点和尾节点都指向新节点
if (head == null) {
head = newNode;
last = newNode;
return;
}
// 1. 原来的尾节点的 next 指向新节点
last.next = newNode;
// 2. 新节点的 prev 指向原来的尾节点
newNode.prev = last;
// 3. 尾节点更新为新节点
last = newNode;
}
/**
* 任意位置插入：在下标 index 处插入新节点（下标从 0 开始）
* @param index 插入位置
* @param data 插入数据
*/
public void addIndex(int index, int data) {
int size = size();
// 1. 合法性校验
if (index < 0 || index > size) {
System.out.println("插入下标不合法！");
return;
}
// 2. 复用头插法
if (index == 0) {
addFirst(data);
return;
}
// 3. 复用尾插法
if (index == size) {
addLast(data);
return;
}
// 4. 中间插入：找到 index 对应的节点（cur）
ListNode newNode = new ListNode(data);
ListNode cur = head;
int count = 0;
while (count != index) {
cur = cur.next;
count++;
}
// 5. 建立引用关系（先绑前后，再断旧链，避免数据丢失）
newNode.prev = cur.prev;
newNode.next = cur;
cur.prev.next = newNode;
cur.prev = newNode;
}
/**
* 查找是否包含关键字 key
* @param key 要查找的关键字
* @return 包含返回 true，否则返回 false
*/
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* 删除第一次出现关键字为 key 的节点
* @param key 要删除的关键字
*/
public void remove(int key) {
// 特殊情况1：链表为空
if (head == null) {
System.out.println("链表为空，无法删除！");
return;
}
ListNode cur = head;
// 特殊情况2：头节点是要删除的节点
if (cur.val == key) {
head = head.next;
// 处理链表只有一个节点的情况
if (head != null) {
head.prev = null;
} else {
last = null;
}
return;
}
// 1. 找到要删除的节点
while (cur != null) {
if (cur.val == key) {
break;
}
cur = cur.next;
}
// 2. 判断是否找到
if (cur == null) {
System.out.println("链表中无此关键字，无法删除！");
return;
}
// 3. 处理中间节点和尾节点
cur.prev.next = cur.next;
// 处理尾节点的情况
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
last = cur.prev;
}
}
/**
* 删除所有值为 key 的节点
* @param key 要删除的关键字
*/
public void removeAllKey(int key) {
// 特殊情况：链表为空
if (head == null) {
System.out.println("链表为空，无法删除！");
return;
}
ListNode cur = head;
while (cur != null) {
// 找到要删除的节点
if (cur.val == key) {
// 处理头节点
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
last = null;
}
} else {
// 处理中间节点和尾节点
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
last = cur.prev;
}
}
}
// 当前节点后移
cur = cur.next;
}
}
/**
* 得到链表的长度
* @return 链表节点个数
*/
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
/**
* 打印链表所有数据
*/
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
/**
* 清空链表（安全清空，避免内存泄漏）
*/
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode nextNode = cur.next;
cur.prev = null;
cur.next = null;
cur = nextNode;
}
head = null;
last = null;
}
}
核心优势说明
- 新增
last尾节点：尾插法、删除尾节点无需遍历，效率从 O(n) 提升到 O(1)。 - 双向遍历支持：可通过
prev向前遍历，为后续复杂操作（如逆序打印）提供便利。 - 安全清空：不仅置空
head和last，还逐个置空节点的prev和next，避免潜在内存泄漏。
三、链表使用
掌握了底层模拟实现后，我们来使用 JDK 提供的 LinkedList，它基于双向链表实现，提供了丰富的操作方法，满足日常开发需求。
常用方法演示
import java.util.ArrayList;
import java.util.LinkedList;
public class LinkedListCommonMethods {
public static void main(String[] args) {
// 1. 创建 LinkedList 实例（泛型指定存储 Integer 类型数据）
LinkedList<Integer> linkedList = new LinkedList<>();
// 2. 新增元素
linkedList.add(12); // 尾插元素（默认方法）
linkedList.add(34); // 尾插元素
linkedList.add(2, 45); // 在索引 2 处插入元素（中间插入）
// 3. 批量添加元素
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(999);
linkedList.addAll(arrayList); // 尾插整个集合的元素
// 4. 删除元素
linkedList.remove(2); // 删除索引 2 处的元素
linkedList.remove((Integer) 999); // 删除第一个出现的 999（注意装箱，避免与索引删除混淆）
// 5. 获取和修改元素
int firstElement = linkedList.get(0); // 获取索引 0 处的元素
linkedList.set(0, 888); // 将索引 0 处的元素修改为 888
// 6. 查找元素
boolean contains = linkedList.contains(888); // 判断是否包含 888
int firstIndex = linkedList.indexOf(888); // 获取 888 第一次出现的索引
int lastIndex = linkedList.lastIndexOf(888); // 获取 888 最后一次出现的索引
// 7. 截取子链表（注意：子链表是原链表的视图，修改子链表会影响原链表）
LinkedList<Integer> subList = (LinkedList<Integer>) linkedList.subList(0, 1);
// 8. 打印结果（验证操作）
System.out.println("原链表：" + linkedList);
System.out.println("子链表：" + subList);
// 9. 清空链表
linkedList.clear();
System.out.println("清空后链表：" + linkedList);
}
}
多种遍历方式演示
LinkedList 支持多种遍历方式，其中 ListIterator 支持双向遍历，是其特色之一。
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
public class LinkedListTraversal {
public static void main(String[] args) {
// 初始化链表
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);
// 方式1：普通迭代器（正向遍历）
System.out.println("普通迭代器正向遍历：");
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
// 方式2：ListIterator 正向遍历（支持后续反向遍历，功能更强）
System.out.println("ListIterator 正向遍历：");
ListIterator<Integer> listIterator = linkedList.listIterator();
while (listIterator.hasNext()) {
System.out.print(listIterator.next() + " ");
}
System.out.println();
// 方式3：ListIterator 反向遍历（双向链表的优势体现）
System.out.println("ListIterator 反向遍历：");
ListIterator<Integer> reverseIterator = linkedList.listIterator(linkedList.size());
while (reverseIterator.hasPrevious()) {
System.out.print(reverseIterator.previous() + " ");
}
System.out.println();
}
}
四、相关内部类
在链表模拟实现中，我们使用了静态内部类，而日常开发中还会遇到匿名内部类，这两种内部类在 Java 中应用广泛，这里做简单梳理。
静态内部类
静态内部类是被 static 修饰的内部类，它与外部类的实例无关，仅属于外部类本身。
特点与示例
public class OuterClass {
public int data1; // 实例成员变量
public static int data2; // 静态成员变量
// 静态内部类
static class StaticInnerClass {
public void innerMethod() {
// 静态内部类：无法访问外部类的实例成员变量（data1）
// data1 = 1; // 编译报错
data2 = 100; // 可以访问外部类的静态成员变量（data2）
System.out.println("静态内部类方法执行，data2 = " + data2);
}
}
public static void main(String[] args) {
// 创建静态内部类实例：无需先创建外部类实例，直接通过外部类.内部类创建
OuterClass.StaticInnerClass staticInner = new OuterClass.StaticInnerClass();
staticInner.innerMethod(); // 调用内部类方法
}
}
核心要点
- 访问权限：无法访问外部类的实例成员，只能访问静态成员。
- 实例创建：无需依赖外部类实例，直接创建。
- 应用场景：当内部类与外部类的实例无关，仅为封装相关逻辑（如链表的节点）时使用。
匿名内部类
匿名内部类是没有类名的内部类，它在声明的同时完成实例化，只能使用一次，常用于简化接口/抽象类的实现。
特点与示例
// 定义一个接口
interface Greeting {
void greet();
}
public class OuterClassAnonymous {
public static void main(String[] args) {
// 匿名内部类：实现 Greeting 接口，同时完成实例化
Greeting greeting = new Greeting() {
// 匿名内部类中可以定义成员变量
private int count = 1;
@Override
public void greet() {
System.out.println("Hello, LinkedList! 这是第 " + count + " 次问候");
count++;
}
}; // 注意：匿名内部类末尾必须加分号
// 调用匿名内部类的方法
greeting.greet();
}
}
核心要点
- 无类名：无需单独定义类，直接实现接口/继承抽象类。
- 一次实例化：声明与实例化同时完成，只能创建一个实例。
- 应用场景：快速实现简单的接口/抽象类，无需复用（如事件监听、线程创建）。