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

crcmnpdw  于 2023-04-10  发布在  Java
关注(0)|答案(1)|浏览(110)

我目前正在练习数据结构,我试图删除一个作为参数传递给方法的节点。该方法应该在列表中搜索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;
    }

目前,我的代码只删除了我试图删除的节点之后的节点。我不知道如何将要删除的节点之前的节点指向它之后的节点。感谢任何帮助,因为我在这里卡住了!

06odsfpq

06odsfpq1#

在遍历列表时,还需要跟踪前一个节点。当找到需要删除的节点时,更新前一个节点的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;
}

相关问题