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

Question

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

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;
}