如何在不使用内置 LinkedList 类的情况下实现单链表节点的搜索与删除-java教程-PHP中文网

如何在不使用内置 LinkedList 类的情况下实现单链表节点的搜索与删除

本文详解如何手动实现单链表中按值查找并安全删除指定节点的操作，重点解决“无前驱引用时如何断开链接”的核心难点，并提供健壮、边界完备的 java 实现。

本文详解如何手动实现单链表中按值查找并安全删除指定节点的操作，重点解决“无前驱引用时如何断开链接”的核心难点，并提供健壮、边界完备的 java 实现。

在自定义单链表（如本例中的 Song 节点链）中删除目标节点，关键在于维护对前驱节点（prev）的引用——因为单向链表中每个节点仅持有后继指针（next），无法反向访问其前一个节点。若仅用当前节点 temp 迭代，当匹配到待删节点时，已无法修改其前一个节点的 next 字段，导致逻辑断裂（如原代码中错误地执行 temp.next = song.next，实际修改的是目标节点之后的链接，而非跳过目标节点本身）。

正确的做法是：在遍历过程中同步记录当前节点的前驱。特别要注意首节点（first）的删除需单独处理，因其前驱为 null，必须直接更新 Playlist.first 引用。

以下是修正后的完整 remove 方法实现：

public int remove(Song song) {
    int index = 0;
    Song temp = first;
    Song prev = null;

    // 情况1：空链表或首节点即为目标节点
    if (temp != Song.END && temp.equals(song)) {
        first = temp.next;
        return index;
    }

    // 情况2：从第二个节点开始遍历（prev 初始化为 first）
    prev = first;
    temp = first.next;

    // 注意终止条件：避免无限循环（利用 Song.END 的自环特性）
    while (temp != Song.END && temp != temp.next) {
        if (temp.equals(song)) {
            prev.next = temp.next; // 关键：用 prev 跳过 temp
            return index + 1;
        }
        prev = temp;
        temp = temp.next;
        index++;
    }

    return -1; // 未找到
}

关键改进与注意事项：

✅ 显式追踪前驱：引入 prev 变量，在每次移动 temp 前更新 prev，确保匹配时能准确修改 prev.next；
✅ 首节点特判：直接比较 first 并更新 first 引用，避免空指针或逻辑遗漏；
✅ 终止条件严谨：使用 temp != Song.END 替代模糊的 !temp.equals(temp.next)，因 Song.END 是自环节点（next == this），可作为自然终点；

⚠️ equals 方法风险提示：当前 Song.equals() 未重写 Object.equals(Object)，且未校验 null。建议增强为：

@Override
public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null || getClass() != obj.getClass()) return false;
    Song song = (Song) obj;
    return Objects.equals(title, song.title) && 
           Objects.equals(artist, song.artist);
}