C语言 从单链表和双链表中删除一个随机节点

Question

我很难想出从双链表和单链表中删除一些节点的逻辑。我在网上找过帮助，但我找不到一个简单的例子。以下是我的文件:

---

双链接删除。dCurrent是我们要删除的节点。

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

---

这是我对单链表的理解。同样，sCurrent是要删除的节点。和sPrev = sCurrent->prev .

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

---

问题是，在我从两个列表中删除随机节点的集合后，双链表从头到尾正确显示，但尾到头不正确。单链表也不能正确显示

Answer 1

你的双链表逻辑在我看来很好。我唯一关心的是，如果dCurrent是列表中唯一的元素，那么:

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

很可能会尝试引用空指针。(这取决于你如何设计你的清单。但是在一个典型的设计中，如果dCurrent是唯一的节点，那么dCurrent->next就是NULL。

你的单链表逻辑对我来说也很好，在抽象中，假设"sPrev = current ->prev";但我不明白这个假设怎么可能是正确的。如果它是一个单链表，那么sCurrent没有有一个prev指针。

Answer 2

我能看到的唯一问题是，你的代码将不能正常工作的情况下，头或尾更新为NULL。

基本上，如果您删除唯一的节点，dHead将指向null，因此您需要在后续语句(如

)周围放置"警卫"。

dHead->prev = NULL;

一样

if (dHead != NULL) {
  dHead->prev = NULL;
}

"绕过"这么多条件的一种方法是分配一个NIL(不是类型)元素。

NIL是取代NULL的"节点"。它表示"离开列表的数据部分"，所以它的下一个总是NIL(循环引用)，它的前一个总是NIL(循环引用)。在这种情况下，您要确保NIL永远不能在列表之外访问，并且head->prev == NIL和tail->next == NIL。这样就可以避免许多if (tail != null) { ... }类型语句。

在这样的构造下，空列表是head == NIL && tail == NIL。这大大减少了if (something == null)语句的数量，但您仍然需要考虑一个if语句，当head为NIL时(在删除某些内容后)，您需要将tail设置为NIL以保持一致性。