0

所以我试图从java中的链表中删除一个项目。我没有使用java的预定义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;

    }
4

3 回答 3

1

好吧，如果您的列表为空，则执行开头的 if 语句将立即给出 NullPointerException（因为 current 将为 null）。一般来说，对于LinkedList删除方法，必须考虑三种情况：size == 0、size == 1、size > 1（其中size是Linked List的节点数）。

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。希望这可以帮助。

于 2013-10-30T17:13:56.847 回答
0

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

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？如果您实现 length 只是返回一些通过在向列表中添加值时增加来维持的数字，那么您也应该在删除一个值时减少它。如果 length 遍历列表以找到元素的数量，那么它就可以了，尽管效率不是很高。

最后一条评论：当给定的regN. 为什么？因为你总是删除一个元素。此外，您可能需要重新考虑循环内部的逻辑。目前，如果要删除的元素是第二个元素并且有 1000000 个元素，您将运行循环近 1000000 次。

于 2013-10-30T13:39:08.793 回答
0

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

我刚刚意识到您正在尝试使用 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;

于 2013-10-30T13:43:45.107 回答