从双向链表中删除一个节点

Question

我已经看过这个话题的其他线程，但没有能够使用它们来解决我的问题。

---

这是在链接列表中的节点的主类定义：

class node { 

public: 

    // default constructor 
    node() {name = ""; prev = NULL; next = NULL;}; 

    // default overloaded 
    node(string s) {name = s; prev = NULL; next = NULL;}; 

    // item in the list 
    string name; 

    // links to prev and next node in the list 
    node * next, * prev; 

}; 

---

以上是节点类的定义，这是在其产生链表另一类使用。链表代码给了我们，我们必须修改，所以我知道它的工作原理。我已经完成并测试了双向链表中新增节点的工作，现在我正在从这个双向链表中删除节点。

功能删除一个节点：http://pastebin.com/HAbNRM5W

^这是我需要帮助的代码中，有太多的重复键入

---

我被我的老师告诉记者，该代码，问题是行56，它读取：

tmp->prev = prev; 

我想设置链接到前一个节点是正确的。我尝试使用类似的if/else循环的情况是当前节点是否是列表中的最后一项。如果它是最后一项（又名curr->next = NULL），则不要使用curr->next设置链接并停止循环迭代。

任何帮助/想法/建议/反馈将不胜感激！

void linkedList::remove(string s) 
{ 
     bool found = false; 
     node * curr = getTop(), * prev = NULL; 
     node * tmp = new node(); 
     while(curr != NULL) 
     { 
       // match found, delete 
       if(curr->name == s) 
       { 
         found = true; 
         // found at top 
         if(prev == NULL) 
         { 
          node * temp = getTop(); 
          setTop(curr->next); 
          getTop()->prev = NULL; 
          delete(temp); 
         } // end if 
         else 
         { 
          // determine if last item in the list 
          if (curr->next = NULL) 
          { 
           // prev node points to next node 
           prev->next = curr->next; 
           // delete the current node 
           delete(curr); 
          } // end if 
          // if not last item in list, proceed as normal 
          else 
          { 
           // prev node points to next node 
           prev->next = curr->next; 
           // set the next node to its own name 
           tmp = prev->next; 
           // set prev-link of next node to the previous node (aka node before deleted) 
           tmp->prev = prev; 
           // delete the current node 
           delete(curr); 
          } // end else 
         } // end else 
        } // end if 

       // not found, advance pointers 
       if(!found) 
       { 
        prev = curr; 
        curr = curr->next; 
       } // end if 

       // found, exit loop 
       else curr = NULL; 
     } // end while 

     if(found) 
      cout << "Deleted " << s << endl; 
     else 
      cout << s << " Not Found "<< endl; 
} // end remove 

Answer 1

对于你的代码，我建议几件事。隔离代码以查找具有您正在查找的名称的节点。删除方法应该只删除一个双向链接的节点，只要它给出一个。

我知道你的remove方法需要一个字符串参数，但将它传递给另一个函数，并让该函数返回你正在寻找的节点。

它应该是这个样子：

Node *cur = find("abcd"); 
Node *prev = cur->prev; 
prev->next = cur->next; 

Node *n = cur->next; 
n->next = cur->prev; 

cur->next = NULL; //or nullptr 
cur->prev = NULL; //or nullptr 

delete cur; 

Answer 2

NULL应nullptr

if (curr->next = NULL) { ... 

这是一个任务所取代，你想：

if (curr->next == nullptr) { ... 

在线47我想你说：如果prev == nullptr和next是不nullptr，但你使用

prev->next = curr->next; 

哪一个不行，因为prev是nullptr。

Answer 3

应该像这样：

prev->next = curr->next; 
prev->next->prev = prev; 
delete (curr); 

Answer 4

我在所有不同的条件语句迷路了。所有你需要做的是：

void linkedList::remove(const std::string& s) 
{ 
    node* current = getTop(); // get head node 
    while (current != nullptr) // find the item you are trying to remove 
    { 
     if (current->name == s) 
     { 
      break; // when you find it, break out of the loop 
     } 
    } 

    if (current != nullptr) // if found, this will be non-null 
    { 
     if (current->prev) // if this is not the head node 
     { 
      current->prev->next = current->next; 
     } 
     else 
     { 
      // update head node 
     } 

     if (current->next) // if this is not the tail node 
     { 
      current->next->prev = current->prev; 
     } 
     else 
     { 
      // update tail node 
     } 

     // at this point, current is completely disconnected from the list 
     delete current; 
    } 
}