双链表删除第一次出现法

Question

有人能帮我为这个双链接列表写一个RemoveFirstOccurse方法吗？

它删除目标数据第一次出现的节点。搜索从头部开始。如果目标数据不在列表中，那么列表保持不变。最后一个节点的下一个字段值为null。没有尾部引用。

public class DoublyLinkedList {

    protected Node head; // Note there is no tail reference.
    public void addToFront(String data) {
        head = new Node(data, head, null);
        if(head.next != null) {
            head.next.previous = head;
        }

    public void removeFirstOccurrence(String data) { 
    }

    protected class Node {
        protected String data;
        protected Node next;
        protected Node previous;
        private Node(String data, Node next, Node previous) {
            this.data = data;
            this.next = next;
            this.previous = previous;
        }
        private Node(String data) {
            this(data, null, null);
        }
    } // end of Node class 
} // end of DoublyLinkedList class

到目前为止，我写了这样的东西，但是当删除列表中没有的字符串时，我得到了一个空指针异常。我已经标记了NPE发生的地方。如果你能帮助找出原因，或者如果你有一个完全不同的方法来工作，那也没关系，请告诉我，谢谢！

public void removeFirstOccurance(String data) {
    if (data.equals(null)) {
        throw new java.lang.IllegalArgumentException("Data is null");
    }
    if (head == null) {
        throw new java.util.NoSuchElementException("List is empty");
    }

    Node current = head;
    if (current.data.equals(data)) {
        head = current.next;
    } else {
        boolean found = false; //keeps track if we found the element
        while (current != null && !found) {
            if (current.next.previous == null) { //NPE here
                current.next.previous = current;
            }
            current = current.next;
            if (current.data.equals(data)) {
                found = true;
                if (current.next == null) {
                    current.previous.next = null;
                } else {
                    current.previous.next = current.next;
                }
            }
        }
    }
}

Answer 1

在访问循环中的current.next值之前，您没有测试它。因此，当到达列表的末尾时，会发生异常。

while (current != null && !found) { // testing current
    if (current.next.previous == null) { // accessing current.next + testing current.next.previous
        current.next.previous = current;
    }
    // your loop
}

注意：这看起来像是工作任务，所以我不会发布代码。

Answer 2

这就是我帮助你找到bug的理由。计算current时发生空指针异常。下一个以前的。上一行确保当前！=空。因此，很可能是当前的。接下来是空值。测试这一点的一个简单方法是添加assert current。下一个！=在使用该值之前，为空。如果这个理论是正确的，那么断言异常将在此时抛出。然后，你可以开始检查你的其他代码，找出为什么current。next此时可能为空。

作为编程技巧，我建议您使用大量的assert语句。从长远来看，它们会帮你省去很多痛苦。对于阅读代码的其他人来说，它们也是一个很好的提示，告诉他们您假设的条件在每一点上都是正确的。

Answer 3

只是一些提示，因为我甚至没有在这台机器上安装Java来检查代码。

我建议你把注意力集中在你必须做的事情上：找到第一件事。然后，一旦找到它：更新前面和后面节点的指针。

在我看来，你似乎忘记更新当前的。当前的上一个指针。下一步检查数据是否位于第一个节点时。这样就不会真正删除节点。。

所以，我的方法是有这样的东西

while(!current.data.equals(data) && current.next != null){
    current = current.next; // looking through the list
}

然后，仔细检查您是否还没有到达列表的末尾，更新指针，以便

current.previous.next = current.next;
current.next.previous = current.previous;

还请注意，如果只是为了复制一个值，您不需要将null视为特殊的东西。我的意思是在最后一个if中：

if (current.data.equals(data)) {
                found = true;
                if (current.next == null) {
                    current.previous.next = null;
                } else {
                    current.previous.next = current.next;
                }
            }

您可以简单地将指定为当前。以前的下一个=当前。其次

希望这有帮助。