如何正确删除双链表中的节点？

Question

void SinglyLinkedList::removeBike(int c)
{
   Node* current = head;

   for(int i = 0; i < c; i++){         // traverse to desired node
       current = current -> next;
   } 

   if(current -> next != NULL && current -> prev != NULL){
        current -> prev -> next = current -> next;
        current -> next -> prev = current -> prev;
        delete current;                     //delete node
   }
   else if(current -> next == NULL){
      current -> prev -> next = current;
      delete current;
   }
   else if(current -> prev == NULL){
       current -> next -> prev = current;
       delete current;
   }    
   else 
       cout << "How did you make it this far?";

}

我很确定我在这里不了解一些东西,但到目前为止研究还没有帮助.

从逻辑上讲,它对我来说很有意义,但我觉得这样做太简单了,事实并非如此.

编辑:更新代码减去输入检查,当我输入任何int时它打破了我.我也应该把这个类重命名为双重链表......只是注意到了

Answer 1

不,这绝对不是那么简单.

首先,如果c参数超出了列表的大小,当你的current指针击中最后一个节点上的空指针时,你会用空指针取消引用,并吹过它.

然后,如果c为0或列表的最后一个元素的索引,则它prev或它的next指针相应地将为null,并且您还将使用空指针解除引用.

current -> prev -> next = current -> next;
current -> next -> prev = current -> prev;

If current是列表中的第一个元素,current->prev显然会为null.如果current是列表中的最后一个元素,那么current->next显然是null.猜猜当你试图取消引用空指针时会发生什么？

结论:

A)检查函数的输入参数是否有效.

B)当要删除的节点是双向链表中的第一个或最后一个节点时,提供特殊处理.

编辑:根据受欢迎的要求,有人想知道如何解决这个问题:

void SinglyLinkedList::removeBike(int c)
{
   Node* current = head;

   for(int i = 0; i < c; i++){
       if (!current)
           break;
       current = current -> next;
   } 

   if (!current)
           return; // Or throw an exception. Or return a bool false, maybe.

   if (current->prev)
       current -> prev -> next = current -> next;
   else
       head=current->next;

   if (current->next)
       current -> next -> prev = current -> prev;
   else
       tail=current->prev;  // Assuming that there's a tail, somewhere around here...
   delete current;                      //delete node

   // Maybe "return true;" here...
}