Java单链表操作全解：增删改查与核心算法实现
单链表是Java中最基础且重要的线性数据结构之一。本文将从原理出发，结合具体案例详细讲解单链表的创建、遍历、插入（尾插与有序插入）、修改、删除等核心操作，并深入剖析包括链表反转、逆序打印在内的常见面试题解法，提供可运行的Java源码参考。
单链表的结构性基础
单链表（Linked List）由一系列节点组成，每个节点包含两部分数据：存储实际信息的“数据域”和指向下一个节点地址的“指针域”。与数组不同，链表在内存中不需要连续的存储空间，这使得它在动态增减元素时具有更高的灵活性，但也牺牲了随机访问的效率。
理解单链表的关键在于“头节点”的概念。通常在实现中会设置一个不存放实际数据的头节点（Head Node），它的作用是固定链表的入口，使得对第一个实际数据节点的插入和删除操作逻辑统一，无需特殊处理空链表或首节点的情况。
单链表的核心操作方法
为了直观演示单链表的运作机制，以下将以一个模拟“水浒英雄排行榜”的管理系统为例，涵盖节点的定义以及增、删、改、查四大基础功能。
第1步：定义节点类与初始化链表
首先需要定义代表英雄的 HeroNode 类，包含编号 no、姓名 name、昵称 nickname 以及指向下一节点的 next 引用。随后创建管理链表的 SingleLinkedList 类，并初始化一个空的头节点。
第2步：实现节点的添加（尾插法与有序插入）
添加节点主要有两种方式：
- 尾插法（无序添加）： 遍历链表直至找到
next为null的最后一个节点，将其next指向新节点。 - 有序插入（按编号排序）： 通过辅助指针
temp寻找插入位置的前一个节点。若发现目标编号已存在，则插入失败并提示；否则将新节点插入到temp之后，即heroNode.next = temp.next; temp.next = heroNode;。
第3步：实现节点的修改与删除
修改操作： 根据节点编号 no 遍历链表找到对应节点，更新其信息。需注意判断链表是否为空以及节点是否存在。
删除操作： 同样先遍历找到待删除节点的前驱节点 temp。确认找到后，直接让 temp.next = temp.next.next，将被删除节点从链条中摘下。这种“前驱指向后继”的技巧避免了需要持有前驱引用的复杂逻辑。
第4步：完整代码实现与应用示例
以下是完整的 Java 实现代码，整合了上述所有逻辑，可直接复制运行测试。
public class SingleLinkedListDemo {
public static void main(String[] args) {
// 1. 创建英雄节点对象
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// 2. 创建链表管理器
SingleLinkedList singleLinkedList = new SingleLinkedList();
// 3. 按序号插入节点
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
// 显示当前链表状态
System.out.println("初始状态:");
singleLinkedList.list();
// 4. 测试修改：将2号节点信息更改
HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
singleLinkedList.update(newHeroNode);
System.out.println("\n修改后的链表情况~~");
singleLinkedList.list();
// 5. 测试删除：依次删除1、4、3、2号节点
singleLinkedList.del(1);
singleLinkedList.del(4);
singleLinkedList.del(3);
singleLinkedList.del(2);
System.out.println("\n删除后的链表情况~~");
singleLinkedList.list();
}
}
// 定义管理单向链表的类
class SingleLinkedList {
// 初始化头节点，不存放具体数据，作为固定入口
private HeroNode head = new HeroNode(0, "", "");
// 添加节点：无序（追加到末尾）
public void add(HeroNode heroNode) {
HeroNode temp = head;
while (true) {
if (temp.next == null) break;
temp = temp.next;
}
temp.next = heroNode;
}
// 添加节点：按编号顺序插入
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) break; // 到达末尾
if (temp.next.no > heroNode.no) break; // 位置找到
else if (temp.next.no == heroNode.no) {
flag = true; // 编号重复
break;
}
temp = temp.next;
}
if (flag) {
System.out.printf("准备插入的英雄的编号 %d 已经存在，不能加入\n", heroNode.no);
} else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改节点信息（根据编号no）
public void update(HeroNode newHeroNode) {
if (head.next == null) {
System.out.println("链表为空~~");
return;
}
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) break;
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.printf("没有找到编号 %d 的节点\n", newHeroNode.no);
}
}
// 删除节点（根据编号no）
public void del(int no) {
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) break;
if (temp.next.no == no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.printf("要删除的 %d 节点不存在\n", no);
}
}
// 遍历显示链表
public void list() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while (true) {
if (temp == null) break;
System.out.println(temp);
temp = temp.next;
}
}
}
// 定义节点类
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}单链表常见算法与面试题解析
掌握基础 CRUD 操作后，单链表的变种操作是面试中的高频考点。以下介绍四种典型算法。
第1步：获取单链表中有效节点的个数
注意：如果是带头结点的链表，计算时应排除头节点本身，只统计实际存储数据的节点。
// head 为头节点
public static int getLength(HeroNode head) {
if (head.next == null) return 0;
int length = 0;
HeroNode cur = head.next;
while (cur != null) {
length++;
cur = cur.next;
}
return length;
}第2步：查找倒数第K个节点
该算法通常要求遍历一次或两次链表。基础思路是：先遍历得到总长度 size，第二次遍历时定位到 size - index 处的节点。需校验 index 的有效性。
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head.next == null) return null;
int size = getLength(head);
if (index <= 0 || index > size) return null;
HeroNode cur = head.next;
for (int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;
}第3步：单链表的反转（头插法重构）
这是难度较高的题目。核心思路是建立一个新的虚拟头节点 reverseHead，遍历原链表，将每个节点摘下，并使用头插法插入到新链表头部。最终将原头节点的 next 指向新链表的第一个有效节点即可。
public static void reverseList(HeroNode head) {
if (head.next == null || head.next.next == null) return;
HeroNode cur = head.next;
HeroNode next = null;
HeroNode reverseHead = new HeroNode(0, "", "");
while (cur != null) {
next = cur.next; // 暂存下一个节点
cur.next = reverseHead.next; // 当前节点指向新链表的头部
reverseHead.next = cur; // 新链表头部指向当前节点
cur = next; // 移动游标
}
head.next = reverseHead.next; // 连接反转后的链表
}第4步：从尾到头打印单链表
若要逆序输出而不破坏链表结构，推荐使用栈（Stack）数据结构。将所有节点依次压入栈中，利用栈“后进先出”的特性弹出节点进行打印。另一种方法是先反转链表再正向遍历，但会改变原链表结构，仅在允许修改原结构时使用。
import java.util.Stack;
public static void reversePrint(HeroNode head) {
if (head.next == null) return;
Stack stack = new Stack<>();
HeroNode cur = head.next;
// 压栈
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 弹栈打印
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
} 以上就是Java数据结构与算法之单链表深入理解的详细内容，更多关于Java单链表应用技巧的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
