DoublyLinkedList 节点操作未按预期工作，为 .prev 函数提供了错误的节点数据

Question

我目前正在为我的 DLList 程序编写 deleteAt() 函数，尽管为了尝试删除堆栈中间的一个节点，代码的行为不可预测，我不知道为什么？

对于之前创建的包含数字的列表： 2 , 3 , 9 , 8 , 7 , 4

和删除节点位置数据的操作：2（数字9）

我的代码行为很奇怪，它不是简单地删除位置 2 的数据，而是删除位置 2 和 1 的数据，所以结果是：2,8,7,4

当使用 diplayNode() 函数时，我发现代码行 DLLNode p = posFind.prev;而不是在那个特定的迭代中给我 posFind 之前的节点的数据，它总是给我数据就像 posFind == head.next, 因此它总是 return 'head'

的数据

而且我不知道为什么会发生这种情况，因为当我在嵌套的 if() 语句中使用 displayNode() 函数时，它 return 向我提供了在该特定迭代中 posFind 的正确数据？

知道为什么会这样吗？

代码：

while (i < count) {
    if (i == pos) {
        DLLNode tmp = posFind.next;
        posFind.next = current;
        current.prev = head;  
        current.next = tmp;
        tmp.prev = current;
    }
    posFind = posFind.next;
    i++;
}

Answer 1

代码中有几个小错误。原则上，解决方案归结为以下内容：

public void deleteAt(int pos) {
    if (0 > pos || pos >= count) {
        return false;
    }
    DLLNode node = nodeAt(pos);
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next;
    }
    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev;
    }
    --count;
    return true;
}

private DLLNode nodeAt(int pos) {
    if (0 > pos || pos >= count) {
        throw new IndexOutOfBoundsException();
    }
    DLLNode node;
    if (pos <= count/2) {
        node = head;
        for (int i = 0; i < pos; ++i) {
            node = node.next;
        }
    } else {
        ...
    }
    return node;
}

Class 不变量：

在您努力进行单元测试时，我想提一下前置条件和 post 条件的使用。特别是不变量必须在之前和之后任何操作。

assert (head == null && tail == null && count == 0)
    || (head != null && tail != null && count > 0);

assert (node.prev == null && head == node)
    || (node.prev != null && node.prev.next == node);

assert (node.next == null && tail == node)
    || (node.next != null && node.next.prev == node);

Answer 2

找到威利了！

错误在insertBefore。你有

while (i < count) {
    if (i == pos) {
        DLLNode tmp = posFind.next;
        posFind.next = current;
        current.prev = head;  <----- here!!!
        current.next = tmp;
        tmp.prev = current;
    }
    posFind = posFind.next;
    i++;
}

但是标线应该是

current.prev = posFind;

将反向指针设置为 head 会弄乱每个非结束插入。

DoublyLinkedList 节点操作未按预期工作，为 .prev 函数提供了错误的节点数据

DoublyLinkedList node operation not working as expected, giving wrong node data for .prev function

java

nodes

doubly-linked-list