链表的remove()方法

Question

我正在上一门编程课，我有以下任务。

编写一个菜单驱动程序，接受单词和它们的含义，或按字典顺序显示单词列表。当要向字典添加条目时，必须先输入单词作为一个字符串，然后分别输入含义。另一个要求是，有时单词会过时。当这种情况发生时，必须从字典中删除这个单词。

使用 JOptionPane 类来输入信息。

使用链表的概念来完成这个练习。您将需要至少以下类：

WordMeaning 类，保存单词的名称和意义。 WordMeaningNode 类，创建信息节点及其链接字段。 WordList 类，创建并维护单词及其含义的链接列表。 Dictionary 类，测试您的类。

对于输出，程序应该生成两个可滚动的列表：

当前单词及其含义的列表。 已删除单词的列表。不需要列出含义，只需列出单词即可。

到目前为止，我已经编写了除了 remove 方法之外的所有代码，而且我不知道如何编写那个方法，请问有谁能帮助我吗？我已经编写了 add 方法，但现在我不知道从 WordList 类的哪里开始编写 remove 方法。我的类如下所示。

WordList 类：

public class WordList {

WordMeaningNode list;

WordList() {
    list = null;
}

void add(WordMeaning w)// In alphabetical order
{
    WordMeaningNode temp = new WordMeaningNode(w);

    if (list == null)
        list = temp;
    else
    {
        WordMeaningNode aux = list;
        WordMeaningNode back = null;
        boolean found = false;

        while(aux != null && !found)
            if( temp.getWordMeaning().getName().compareTo(aux.getWordMeaning().getName()) < 0 )
                found = true;
            else
            {
                back = aux;
                aux = aux.next;
            }

        temp.next = aux;
        if (back == null)
            list = temp;
        else
            back.next = temp;
    }
}

boolean listIsEmpty() {
    boolean empty;
    if (list == null) {
        empty = true;
    } else {
        empty = false;
    }

    return empty;
}

public String toString()
{
    String result = "";
    int count = 0;
    WordMeaningNode current = list;

    while (current != null)
    {
        count++;
        result += current.getWordMeaning().getName() + "\n" + "\t" + current.getWordMeaning().getDefinition();
        current = current.next;
    }

    return result + "\nThe number of words is : " + count;
}
}

我尝试使用与添加方法相同的格式来编写删除方法，但并没有起作用，或者我做错了。

- Daniel D

---

不，他的任务是编写一个WordMeaningNodes的链表代码，每个节点包含一个WordMeaning实例，其中包含一个单词及其定义。在发表评论之前请阅读问题。 - Olivier Croisier

Answer 1

从LinkedList中删除一个元素，你需要遍历它的节点。如果找到了要删除的元素，在前一个节点和后一个节点之间建立连接，并设置previous.next = next:

boolean remove(String word) {

    if (list == null)   // list is empty
        return false;

    WordMeaningNode n = list;
    WordMeaningNode prev = null;

    do {
       if (n.wordMeaning.name.equals(word)) {  // word found
           if (prev != null) {
              prev.next = n.next;   // connect previous to next
           } else {
              list = list.next;     // connect head to next
           }
           return true;
       }
       prev = n;
       n = n.next;
    } while (n != null);   // repeat till the end of a list
    return false;
}

在主代码中，更改case 2这一部分：

if (diction.remove(word)) {
    obsolete.add(new WordMeaning(word, " "));
    // notify about deletion
} else {
    // notify that word don't exist.
}

因为这里真的不需要NullPointerException。

- Alex Salauyou

---

不用客气。顺便说一下，链表的头部通常被称为“head”，而不是“list”。 - Alex Salauyou

Answer 2

要从列表中删除一个元素，需要找到要删除的元素之前的元素，并将其next引用设置为要删除的元素之后的元素。

您需要注意一些（不互斥的）特殊情况：

• 如果要删除的元素是第一个（则WordList的第一个节点应设置为要删除的元素之后的元素）
• 如果要删除的元素是列表中的最后一个元素（则必须将前一个元素的next引用设置为null）

此外，我看到你需要保留已删除项的列表，所以在过程中不要忘记保留对已删除项的引用，并将其添加到已废弃单词的列表中。

- Olivier Croisier