0

我很难想出从双链表和单链表中删除某些节点的逻辑。我从帮助中在线查看，但我找不到一个简单的例子。这是我所拥有的：

双链删除。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;
}

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

4

2 回答 2

3

您的双向链表逻辑对我来说看起来不错。我唯一担心的是，如果dCurrent是列表中唯一的元素，那么：

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

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

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

于 2011-11-30T21:00:49.197 回答
0

The only issues I can see is that your code won't function properly for scenarios where head or tail are updated to NULL.

Basically if you delete the only node, dHead will point to null, so you need to put "guards" around subsequent statements like

dHead->prev = NULL;

like so

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

One way to "get around" having so many conditionals is to assign a NIL (not a type) element.

NIL is the "node" which replaces NULL. It represents "off the data portion of the list" so its next is ALWAYS NIL (a circular reference) and it's previous is ALWAYS NIL (a circular reference). In such cases, you ensure that NIL is never accessible outside of the list, and that head->prev == NIL and tail->next == NIL. That way you can avoid the many if (tail != null) { ... } type statements.

Under such a construct, an empty list is one where head == NIL && tail == NIL. This dramatically reduces the number of if (something == null) statements, but you still have one if statement to consider, when head is NIL (after deleting something) you need to set tail to NIL for consistency's sake.

于 2011-11-30T21:06:26.220 回答