链表的 remove() 方法

Question

我正在参加编程class我有以下作业。

编写一个菜单驱动的程序，它要么接受单词及其含义，要么按字典顺序显示单词列表（即在字典中）。当要将条目添加到词典时，您必须首先将单词作为一个字符串输入，然后将其含义作为单独的字符串输入。另一个要求 - 有时单词会过时。发生这种情况时，必须从字典中删除该词。

使用 JOptionPane class 输入信息。

使用 linked 列表的概念来进行这个练习。您至少需要以下 classes：

一个 WordMeaning class 包含单词的名称及其含义。
A WordMeaningNode class 创建信息的节点及其 link 字段。
一个 WordList class 创建和维护一个 linked 的单词列表和它们的含义。
字典 class 测试您的 classes。

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

当前单词列表及其含义。
删除的单词列表。您无需列出含义，只需单词。

到目前为止，除了 remove 方法之外，我已经对所有内容进行了编码，但我不确定如何对其进行编码，所以请任何人帮助我。我已经编写了 add 方法的代码，但现在我不知道从哪里开始我的 WordList class 中的 remove 方法。我的 class 如下。

单词表 Class:

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

我尝试对 remove 方法使用与对 add 方法相同的方法格式，但没有真正起作用，或者我做错了。

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这里。

Answer 2

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

你会有一些（不是互斥的）极端情况需要注意：

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

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

链表的 remove() 方法

remove() method of a linked list

java

linked-list

data-structures