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

本文详解如何手动实现单向链表中指定节点的查找与删除操作，重点解决“删除时需访问前驱节点”这一核心难点，并提供健壮、可运行的 java 代码示例。

本文详解如何手动实现单向链表中指定节点的查找与删除操作，重点解决“删除时需访问前驱节点”这一核心难点，并提供健壮、可运行的 java 代码示例。

在手写链表（如本例中的 Song 节点构成的播放列表）时，删除任意中间节点的关键在于：必须持有被删节点的前驱引用，才能将其 next 指针重定向到被删节点的后继，从而完成逻辑删除。原代码仅维护当前节点 temp，无法修改其前一个节点的 next 字段，因此错误地执行了 temp.next = song.next（实际是让当前节点跳过自己的下一个节点），导致行为错乱。

以下是修正后的 remove(Song song) 方法，已适配你提供的 Song 和 Playlist 结构：

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

    // 特殊处理：头节点即为目标节点
    if (temp != Song.END && temp.equals(song)) {
        first = temp.next;
        return index;
    }

    // 遍历链表（注意终止条件：避免无限循环于 END 节点）
    while (temp != Song.END && temp.next != Song.END) {
        prev = temp;
        temp = temp.next;

        if (temp.equals(song)) {
            prev.next = temp.next; // 前驱节点绕过 temp，指向其后继
            return index + 1;
        }
        index++;
    }

    return -1; // 未找到匹配歌曲
}

⚠️ 关键修正说明：

使用 Song.END 替代 null 作为链表尾标识符，因此循环条件需改为 temp != Song.END && temp.next != Song.END，防止在 END 节点上调用 .equals() 或访问 .next 导致逻辑错误或异常；
显式区分头节点删除（直接更新 first）与中间/尾节点删除（通过 prev.next 修改指针）；
index 在匹配成功时返回 index + 1，因为 temp 在循环中首次进入体时已指向第二个节点（first.next），索引从 1 开始计数；若需统一从 0 开始，可将 index++ 移至匹配判断之后（推荐）；
Song.equals() 方法需增强健壮性：当前实现未处理 other == null 的情况，建议补充空值检查，避免 NullPointerException。

✅ 最佳实践建议：