从 Java LL 中删除特定项

Question

所以我正在尝试从 java 中的链表中删除一个项目。我没有使用java的预定义LL，但我正在使用自己的LL。

我知道删除项目的概念是在链接中遍历并逐个比较列表中的数据。

所以这就是我想出的，但它不起作用！

public void delStudent(int regN) {
    Node current = head;
    Node q = head;
    if (current.getStudent().getRegN() == regN) {
        head = head.link;
    }
        for (int i = 0; i < this.length() - 1; i++) {
            if (current.getStudent().getRegN() != regN) {
                current = current.link;
                q = current;
            }
        }
        q.link= current.link.link;
    }

Answer 1

好吧，如果你的列表是空的，那么开头的if语句的执行将立即给出一个NullPointerException（因为current将是null）。通常，对于 LinkedList 删除方法，您必须考虑三种情况：大小 == 0、大小 == 1 和大小> 1（其中大小是链表中的节点数）。

public void delStudent(int regN) {
    Node current = head;
    Node previous = head;       
    while (current != null ){ // keep traversing till end of list
        if (current.getStudent().getRegN() == regN) { // found it!
            previous.link = current.link; // relink
            if (current == head){ // edge case : removed first element
                head = current.link; // move head forward.
            }
            break;
        } else {
            previous = current;
            current = current.link;
        }   
    }
}

上面的代码假设 regN 是唯一的，并且只有一个学生拥有该 regN。希望这有帮助。

Answer 2

错误在于（我认为）这三行：

current = current.link;
q = current;

（将q设置为与current相同）和

q.link= current.link.link;

（也可能在使用length()，具体取决于它的实现）

要了解原因，让我们更详细地了解如何删除：假设列表中有三个节点 x->y->z，并且您要删除 y。为此，您需要设置 x.link = z .

回到你的例子，这意味着变量q应该在current之前存储元素，然后删除current可以通过以下方式完成

q.link = current.link;

为了使q成为current的前身，您必须颠倒上面的两行，即使用

q = current;
current = current.link;

为什么我说取决于length的实施？如果你的实现长度只是返回一些通过增加来维护的数字，只要你向列表中添加一个值，你也应该在删除一个值时递减它。如果长度遍历列表以找到元素的数量，那么它没关系，尽管效率不是很高。

最后一条评论：当给定regN没有元素时，您的代码将无法工作（即使使用我上面解释的修复程序）。为什么？因为您总是删除一个元素。此外，您可能需要重新考虑循环中的逻辑。目前，如果要删除的元素是第二个元素，并且有 1000000 个元素，您将运行循环近 1000000 次。

Answer 3

当您检查每个节点时，您需要删除该节点或在找到匹配项后中断。您需要为前一个节点维护一个节点，以便在找到匹配项后能够删除当前节点。

我刚刚意识到您正在尝试使用 Node q 来做到这一点

for (int i = 0; i < this.length() - 1; i++) {
    if (current.getStudent().getRegN() != regN) {
        q = current;
        current = current.link;           
    } else{ //we have a match
        //remove the link to the current item
        q.link = current.link; 
        break; 
    }

如果您使用的是双向链表，则可以使用 node.prev（）.link = current.link;