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，因此它总是返回"头"的数据

我不知道为什么会发生这种情况，因为当我在嵌套的if（）语句中使用displayNode（）函数时，它会在特定的迭代中为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

找到Waldo！

错误在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;

将后向指针设置为每一个非末端插入都会出错。

Answer 2

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

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

---

类不变量：

在您进行单元测试时，我想提及前置条件和后置条件的使用。尤其是不变量必须在之前的和之后的中保持。

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