双向链表不再双向链接

Question

我在编写的一段代码中遇到了一些问题，希望有人可以帮助我了解哪里出了问题并解释原因，以便我能更好地理解它。

有人告诉我，我的双向链表不再双向链接，但我看不出哪里出错了。我将在下面包含有问题的代码部分：

public void deleteWithValue(int searchValue)
{
    // Delete the first node in the list with the given value.
    if (head.data == searchValue)
    {
        head = head.next;
        return;
    }
    DoublyLinkedListNode current = head;
    DoublyLinkedListNode prev = current;
    while (current.next != null)
    {
        prev = current;
        current = current.next;
        if (current.data == searchValue)
        {
            prev = current.next;
            current = current.next;
            current.prev = prev;
            break;
        }
    }
}

非常感谢，

杰斯

Answer 1

如果条件 current.data == searchValue 的计算结果为 true，那么您需要为下一个节点更新 prev link，以及 next link为前一个节点顺序在两个方向上保持links。

就目前而言，您没有为 current.prev.next 更新 link，因此您在那个方向上丢失了 link。

此外，您将 head 节点视为特例的方式意味着如果 head 恰好是要删除的节点，则 current.next.prev 不会更新.

改为考虑这个：

public void deleteWithValue(int searchValue) {
    DoublyLinkedListNode current = head;

    while (current != null) {

        // If true, then the current node is the one to remove
        if (current.data == searchValue) {  

            if (current == head) {
                head = head.next;
            }

            // Ensure the previous node maintains a link to the next node
            if (current.prev != null) {
                current.prev.next = current.next;
            }

            // Ensure the next node maintains a link to the previous node   
            if (current.next != null) {
                current.next.prev = current.prev;
            }

            break;
        }
        current = current.next;
    }
}

Answer 2

有两个问题：

John3130 开始打出这个问题：

if (head.data == searchValue)
{
    head = head.next;
    return;
}

在上述情况下，您忘记将 head.prev 设置为 null。

if (head.data == searchValue)
{
    head = head.next;
    if (head != null) {
        head.prev null;
    }
    return;
}

另一个问题是当 head 为 null 时调用 delete 方法。（假设 head==null 表示一个空列表。）在尝试推导 head.data.

时会抛出异常

您实际上根本不需要 "prev" 值。从头开始搜索后，只需对 null 进行明智的检查：

public void deleteWithValue(int searchValue) {

    DoublyLinkedListNode current = head;
    // search
    while ((current != null) && (current.data != searchValue)) {
        current = current.next;   
    }

    if (current != null)  {

        if (current.next != null)  {
           current.next.prev = current.prev;
        }

        if (current.prev != null) {
            current.prev.next = current.next;
        }

        if (current == head) {
            head = current.next;
        }
    }
}

双向链表不再双向链接

Doubly linked list no longer linked in both directions

java

doubly-linked-list