如何在不使用链表类的情况下从该链表中搜索和删除节点？

Question

我目前正在练习数据结构，我正在尝试删除作为参数传递给方法的节点。该方法应该在列表中搜索 arg'd 歌曲，返回节点的索引，并将其从列表中删除。我有点卡住了，无法完全弄清楚如何在没有先前节点数据的情况下删除节点。我不确定这是否可以挽救或者我的方法是否完全错误。

public int remove(Song song) {
        int index = 0;
        Song temp = first;
        while (!temp.equals(temp.next)) {
            if (temp.equals(song)) {
                temp.next = song.next;
                return index;
            }
            temp = temp.next;
            index++;
        }
        return -1;
    }

这是我正在使用的节点的类。

public class Song {
    String title;
    String artist;
    Song next;
    public static final Song END = new Song();

    public Song(String title, String artist){
        this.title = title;
        this.artist = artist;
        next = END;
    }

    // This is used to construct the END Table.
    private Song() {
        title = "";
        artist = "";
        next = this;
    }

    public boolean equals(Song other) {
        if (this.title.equals(other.title) 
         && this.artist.equals(other.artist))
            return true;
        return false;
    }

播放列表类的相关部分

public class Playlist {
    String name;
    Song first;
    public Playlist(){
        name = "library";
        first = Song.END;
    }

    public Playlist(String name) {
        this.name = name;
        first = Song.END;
    }

目前我的代码只删除我试图删除的节点之后的节点。我不确定如何将要删除的节点之前的节点指向它之后的节点。感谢您的帮助，因为我被困在这里了！

Answer 1

您还需要在遍历列表时跟踪前一个节点。当找到需要移除的节点时，更新上一个节点的

next

指针，跳过要移除的节点

所以像：

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

    // check if the first node is the one to be removed
    if (temp != null && temp.equals(song)) {
        first = temp.next;
        return index;
    }

    // iterate through the list and search for the node to be removed
    while (temp != null && !temp.equals(temp.next)) {
        prev = temp;
        temp = temp.next;

        if (temp.equals(song)) {
            prev.next = temp.next;
            return index + 1;
        }
        index++;
    }

    return -1;
}

Answer 2

public int remove(Song song) {
    int index = 0;
    Song prev = first;
    Song temp = first;
    while (!temp.equals(temp.next)) {
        if (temp.equals(song)) {
            if(temp.equals(first))first=temp.next;
            else prev.next = song.next;
            return index;
        }
        prev=temp;
        temp = temp.next;
        index++;
    }
    return -1;
}