Java 单链表核心操作：从节点定义到常见算法实现

单链表的逻辑结构与节点定义

链表不同于数组，它通过每个节点中的引用域指向下一个节点的位置，从而在内存中串联起整个数据序列。一个标准的链表节点通常包含两个部分：

• Data 域（数据域）：用于存储具体的数据元素，在示例中表现为学生的学号 no、姓名 name 和昵称 nickname。
• Next 域（指针域）：用于存储指向下一个节点的地址引用。

根据是否包含不存放数据的虚拟首元节点，链表可分为“带头节点”和“不带头节点”。以下实现采用带头节点的方式，head 节点仅作为入口标志，不参与业务数据存储，这使得插入和删除操作在处理第一个有效节点时逻辑更加统一，无需特殊判断。

首先，我们需要定义单个节点的数据结构：

package linkedQueue;

public 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 + '\'' +
                '}';
    }
}

单链表类的核心功能实现

构建 SingleLinkedList 类来封装链表的操作。该类内部维护一个 head 头节点，并提供一系列方法来操作链表。以下是各功能的详细实现逻辑。

第1步：无序添加节点

目的：将新节点追加到链表的末尾。 操作：通过临时指针 temp 遍历链表，直到找到 next 为 null 的尾节点，然后将新节点的地址赋给 temp.next。

/**
 * 添加节点
 */
public void add(HeroNode heroNode) {
    HeroNode temp = head;
    while (true) {
        if (temp.next == null) {
            break;
        }
        temp = temp.next;
    }
    temp.next = heroNode;
}

第2步：按序添加节点

目的：根据节点的编号（no）保持链表由小到大有序排列。 操作：找到第一个比待插入节点编号大的节点的前驱节点，或者判断编号是否已存在。

/**
 * 有序添加节点
 */
public void addByOrder(HeroNode herNode) {
    HeroNode temp = head;
    boolean flag = false;
    while (true) {
        if (temp.next == null) {
            break;
        }
        if (temp.next.no > herNode.no) {
            break;
        } else if (temp.next.no == herNode.no) {
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag) {
        System.out.println("你要插入的节点的编号已经存在！！！！");
    } else {
        herNode.next = temp.next;
        temp.next = herNode;
    }
}

第3步：修改节点信息

目的：根据节点编号更新其名称或昵称。 操作：从头节点后开始遍历，若找到对应编号则修改属性；若遍历结束未找到则报错。

/**
 * 更新节点数据
 */
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.println("没有找到编号" + newHeroNode.no + "的节点，不能修改");
    }
}

第4步：删除节点

目的：从链表中移除指定编号的节点。 操作：关键在于“间接删除”。遍历寻找目标节点的前一个节点 temp，一旦发现 temp.next 即为目标，执行 temp.next = temp.next.next 跳过该节点，即可完成物理删除。

/**
 * 刪除节点
 */
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;
    }
}

第5步：遍历显示所有节点

目的：检查当前链表中的所有数据。 操作：初始化指针为 head.next，循环输出直至指针变为 null。

/**
 * 遍历节点
 */
public void showList() {
    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;
    }
}

进阶算法：反向打印、计数与反转

反向打印节点

逻辑：由于链表只能向后访问，反向打印可以使用栈（LIFO）特性实现。依次将所有节点压入栈，然后再弹出打印，即可实现倒序输出。

//反向打印节点
public static void reversePrint(HeroNode head) {
    if (head.next == null) {
        return;
    }
    // 创建一个栈
    Stack<HeroNode> heroNodes = new Stack<>();
    HeroNode cur = head.next;
    while (cur != null) {
        heroNodes.push(cur); //入栈
        cur = cur.next;
    }
    // 出栈打印
    while (heroNodes.size() > 0) {
        System.out.println(heroNodes.pop());
    }
}

获取有效节点个数

逻辑：同样通过遍历计数，统计 head.next 开始的节点总数。

/**
 * 统计有效节点的个数
 */
public static int getLength(HeroNode head) {
    if (head.next == null) {
        return 0;
    }
    int length = 0;
    HeroNode herNode = head.next;
    while (herNode != null) {
        length++; 
        herNode=herNode.next;
    }
    return length;
}

查找倒数第 N 个节点

逻辑：先计算链表总长度 size，则倒数第 N 个即正数第 (size - N) 个。校验索引范围后，从头节点后移动相应步数即可。

/**
 * 求倒数第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 herNode = head.next;
    for (int i = 0; i < size - index; i++) {
        herNode = herNode.next;
    }
    return herNode;
}

单链表反转

逻辑：这是单链表最经典的算法题。创建一个新的辅助头节点 reverseHead，原链表每经过一个节点，就将其取出并插入到新链表的头部（reverseHead.next）。最终将原链表的 head.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; // 将cur的下一个节点指向新的链表的最前端
        reverseHead.next = cur;      // 将cur链接到新的链表
        cur = next;                  // 指针后移
    }
    head.next = reverseHead.next; // 连接原链表的新头部
}

以上就是 Java 实现单链表基础操作的详细内容，更多关于 Java 单链表学习资料的关注，请搜索相关技术资料或关注本站其它相关文章！