从单个和双关联列表中删除一个随机节点

Question

我很难提出逻辑，以从双重和单独链接的列表中删除一些节点。我已经从Help上在网上看，但找不到一个简单的例子。这是我所拥有的：

---

双链接删除。 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 = scurrent-> prev”的假设，您的单一链接列表逻辑对我来说也很好。但是我不明白该假设如何正确。如果这是单一连接的列表，那么 sCurrent 不 有 一个 prev 指针。

Answer 2

我唯一可以看到的问题是，对于将头部或尾巴更新为NULL的方案，您的代码无法正常运行。

基本上，如果删除唯一的节点，dhead将指向null，因此您需要将“警卫”围绕后续陈述（如

dHead->prev = NULL;

像这样

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

“四处走动”的一种方法是分配一个零（不是类型）元素。

nil是替代null的“节点”。它代表“列表的数据部分”，因此其下一个始终是nil（圆形引用），并且它的先前是始终为nil（圆形参考）。在这种情况下，您确保在列表之外永远无法访问NIL，并且该标题 - > prev == nil和tail-> next == nil。这样，您可以避开许多 if (tail != null) { ... } 类型语句。

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