双链表删除第一次出现的方法

Question

谁能帮我为这个双向链表写一个 removeFirstOccurrence 方法？

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

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
}

注意：看起来像工作分配所以我不会post代码。

Answer 2

这将是我帮助您找到错误的推理。评估 current.next.previous 时发生空指针异常。您的上一行确保 current != null。因此，current.next 很可能是空值。一个简单的测试方法是在使用该值之前添加 assert current.next != null。如果这个理论是正确的，那么此时将抛出一个断言异常。然后您可以开始检查您的其他代码，找出为什么 current.next 在那个时候可能为 null。

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

Answer 3

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

我建议你专注于你必须做的事情：找到第一个出现的地方。然后，一旦找到它：更新前后节点的指针。

例如在我看来，当您检查数据是否在第一个节点中时，您忘记更新 current.next 的 current.previous 指针。这样你就不会真正删除节点..

所以，我的方法是

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

您可以简单地分配 current.previous.next = current.next;

希望对您有所帮助。

双链表删除第一次出现的方法

doubly linked list remove first occurrence method

java

linked-list