如何正确删除双链表中的节点？ [英] How to delete node in double linked list correctly?

问题描述

  void SinglyLinkedList :: removeBike（int c）
 {
 Node * current = head; 
 
 for（int i = 0; i  current = current  - 下一个; 
} 
 
 if（current  - > next！= NULL&& current  - > prev！= NULL）{
 current  - > prev  - > next = current  - >下一个; 
 current  - >下一页> prev = current  - > prev; 
 delete current; // delete node 
} 
 else if（current  - > next == NULL）{
 current  - > prev  - > next = current; 
 delete current; 
} 
 else if（current  - > prev == NULL）{
 current  - >下一页> prev = current; 
 delete current; 
} 
 else 
 cout<< 你是怎么做到这一点的？ 
 
} 
  

我相当肯定我不明白，但研究还没有帮助到目前为止。

逻辑上它对我有意义，但我觉得这是太简单的工作，这是不是。

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

解决方案

不，这绝对不是那么简单。

首先，如果 c 参数超过列表的大小，指针取消引用，因为你的当前指针会到达最后一个节点的空指针，并吹过它。

，如果 c 是0或列表的最后一个元素的索引，它是 prev 或它的 next 指针，因此，将为null，并且你也会冒出一个空指针引用。

  current  - > prev  - > next = current  - >下一个; 
 current  - >下一页> prev = current  - > prev; 
  

如果 current 列表， current-> prev 将明显为null。如果 current 是列表中的最后一个元素，则 current-> next 显然为null。猜测当你尝试解引用空指针时会发生什么？

结论：

B）当要删除的节点是双向链表中的第一个或最后一个节点时，提供特殊处理。 p>

编辑：根据热门请求，有人想知道如何解决这个问题：

  void SinglyLinkedList :: removeBike（int c）
 {
 Node * current = head; 
 
 for（int i = 0; i  if（！current）
 break; 
 current = current  - >下一个; 
} 
 
 if（！current）
 return; //或抛出异常。或者返回一个bool false，也许。 
 
 if（current-> prev）
 current  - > prev  - > next = current  - >下一个; 
 else 
 head = current-> next; 
 
 if（current-> next）
 current  - >下一页> prev = current  - > prev; 
 else 
 tail = current-> prev; //假设有一个尾部，这里的某处... 
 delete current; // delete node 
 
 //可能return true; here ... 
} 
  

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?";

}

I'm fairly certain I'm not understanding something here, but research hasn't helped so far.

Logically it makes sense to me but I feel like this is too simple to work, which it isn't.

edited: updated the code minus input check and it breaks on me when I input any int. also I should probably rename the class to doubly linked list... just noticed that

解决方案

Nope, it's definitely not that simple.

First of all if the c parameter exceeds the size of the list, you'll blow up with a null pointer dereference, as your current pointer hits the null pointer on the last node, and blows past it.

Then, if c is 0 or the index of the last element of the list, either it's prev or it's next pointer, accordingly, will be null, and you'll also blow up with a null pointer dereference.

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

If current is the first element in the list, current->prev will obviously null. If current is the last element in the list, current->next will obviously be null. Guess what happens when you attempt to dereference the null pointer?

Conclusions:

A) Check that the input parameter to the function is valid.

B) Provide for special handling when the node to be deleted is the first or the last node in the doubly-linked list.

EDIT: by popular request, someone wanted to know how I would fix this:

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

这篇关于如何正确删除双链表中的节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！