C++ 删除链表C++中的节点

Deleting Node in Linked List C++

提问by ron wagner

So I've been searching forums, but im still very new to the language and linked lists so I can barely decipher the results.

所以我一直在搜索论坛，但我对语言和链接列表仍然很陌生，所以我几乎无法破译结果。

basically I made a delete function for my linked list. I can currently Create a list, traverse the list, sort the list, search the list, and insert before any node in the linked list. I recycled some code from the insert to locate the point in the list where I could delete. My main point of confusion is how to link the previous points to the node that is after the one I am deleting.

基本上我为我的链表做了一个删除功能。我目前可以创建一个列表，遍历列表，对列表进行排序，搜索列表，并在链表中的任何节点之前插入。我从插入中回收了一些代码来定位列表中可以删除的点。我的主要困惑点是如何将前面的点链接到我要删除的节点之后的节点。

回答by

I won't write a whole new linked list implementation but i can point out some of the problems with the code for you.

我不会写一个全新的链表实现，但我可以为你指出代码中的一些问题。

The trick is to stay one node ahead of the one you want to delete.

诀窍是在要删除的节点之前保留一个节点。

I have renamed entryto currentfor clarity

我已经改名entry来current为清楚起见

nodetype *current , *first, *next;
int akey;

// With this line your search will start from the second element.
// current =start->ptr;
// Should be
current = start;

// this is not needed. I am assuming the last node has NULL value for '->ptr'
// last=start;
next = current->ptr;

cout<<"Input Data You Would Like To Delete"<<endl;
cin>>akey;

// Check if the first node contains the data
// Assuming the list will have at least one element. i.e. current is not NULL 
while (current->adata == akey)
{
  // Delete it.
  delete current;
  // Update current for the while loop
  current = next;
  // update next too.
  next = current->ptr;
}
// Now we know the first element doesn't contain the data.
// Update the pointer to the begging of the new list if anything is removed from the top.
first = current;

// This has unnecessary checks. 
// ****Specifically (akey!=current->adata) will 
// prevent you from entering the loop if it is false.
// while((akey!=current->adata)&&(current->ptr !=NULL))
while(next != NULL)  // This should be enough
{
     if(next->adata == akey)
     {
          // make the current node (before the 'deletion point') 
          // lined to the one after the 'deletion point (next of the next)
          current->ptr = next->ptr; 
          // delete the node. 
          delete next;
          // Make the next pointer point to the new next. 
          next = current->ptr
     }
    // Otherwise advance both current and next.
     else {
           current = next;
           next = next->ptr; 
     }
}

// Use this to test it.
current = first;
while(current){
    cout<<current->adata<<", ";
    current = current->ptr;
}

This is not the cleanest way. However it is similar to your implementation so you can see where you went wrong.

这不是最干净的方式。但是，它与您的实现类似，因此您可以看到哪里出错了。

回答by Wug

#include <iostream>
#include <string>
                                         // blank line(s) after includes

using namespace std;                     // some people will say to avoid this
                                         // but I use it in examples for brevity

                                         // blank line(s) around class def
class nodetype
{                                        // bracket on its own line
public:                                  // non indented visibility specifier
    nodetype(int value, nodetype *p)     // constructor first declared in class
    {
        adata = value;                   // level of indentation for fn body
        ptr   = p;                       // spaces around operators like =
    }
                                         // blank line(s) between fns and vars
    int adata;
    nodetype *ptr;
};
                                         // blank line(s) between class and fn
void LinkedListDelete(nodetype **start, int akey)
{
    nodetype *current, **previous;       // pointer *s are connected to vars
                                         // blank line between section
    previous = start;
    current  = *start;
                                         // blank line between section
                                         // I use blank lines a lot, they help
                                         // me to organize my thoughts

    while((current != NULL) && (akey != current->adata))
    {                                    // indentation inside nested scope
        previous = &current->ptr;        // no space for unary operators like &
        current  = current->ptr;         // assignments justified to same level
    }

    if (current != NULL)
    {
        *previous = current->ptr;        // no space for unary *, space for =
        delete current;
    }
                                         // more blank lines between sections
    return;
}

void LinkedListPrint(nodetype *list)     // no space for unary *
{                                        // brackets on their own lines
    while (list != NULL)                 // space around !=
    {
        cout << "(Node: " << list->adata << ") ";
        list = list->ptr;                // spaces around <<
    }
    cout << endl;
}

int main()
{
    nodetype *node = new nodetype(5, new nodetype(10, // justified stuff
                     new nodetype(7, new nodetype(14,
                     new nodetype(23, NULL)))));
                                         // blank lines
    cout << "Build linked list: ";
    LinkedListPrint(node);
    cout << "Removed node 7: ";
    LinkedListDelete(&node, 7);
    LinkedListPrint(node);

    return 0;
}

I made this code based on the code you provided. It's not quite the same, I changed some things, but it does what you want it to. I had to guess what the structure of nodetype was, and I added a constructor for my convenience. I added some comments pointing out aspects of my style.

我根据您提供的代码制作了此代码。它不完全相同，我改变了一些东西，但它做你想要的。我不得不猜测 nodetype 的结构是什么，为了方便起见，我添加了一个构造函数。我添加了一些评论，指出了我风格的各个方面。

Notice that it's easier to read than the code you originally provided. Style is important. People will tell you that you have to use X or Y style, but what really matters is that you pick whatever style you like and stick to it consistently; it will make it easier for you to read and understand your own code quickly.

请注意，它比您最初提供的代码更易于阅读。风格很重要。人们会告诉你，你必须使用 X 或 Y 风格，但真正重要的是你选择任何你喜欢的风格并坚持下去；它将使您更容易快速阅读和理解自己的代码。

Believe me you, when you've written a lot of code, you stop being able to remember all of it at once, and being able to figure out what you were doing quickly is essential.

相信我，当您编写了大量代码时，您将无法一次记住所有代码，而能够快速弄清楚自己在做什么是必不可少的。

回答by Deepu

Consider the structure given below,

考虑下面给出的结构，

struct info
{
 int data;
 struct info *next;
};

if you use the above structure to store records in your linked list, then the following code can be used to delete elements from your linked list,

如果您使用上述结构在链表中存储记录，则可以使用以下代码从链表中删除元素，

void delitem()
{
  info *curr,*prev;
  int tdata;
  if(head==NULL)
  {
    cout<<"\nNo Records to Delete!!!";
  }
  cout<<"\nEnter the Data to be deleted: ";
  cin>>tdata;
  prev=curr=head;
  while((curr!=NULL)&&(curr->data!=tdata))
  {
    prev=curr;
    curr=curr->next;
  }
  if(curr==NULL)
  {
    cout<<"\nRecord not Found!!!";
    return;
  }
  if(curr==head)
  {
    head=head->next;
    cout<<"\nData deleted: "<<tdata;
  }
  else
  {
    prev->next=curr->next;
    if(curr->next==NULL)
    {
      temp=prev;
    }
    cout<<"\nData deleted: "<<tdata;
  }
  delete(curr);
}

回答by Deepu

I think it is too simple and easy to delete a node or insert ine in linked-list but it requires precise understanding of its MECHANISM. this example shows how to add and remove nodes however it is not a full program but it reveals the mechanism of adding and deleting and moving alinked-list:

我认为删除节点或在链表中插入ine太简单易行，但需要准确了解其机制。这个例子展示了如何添加和删除节点，但它不是一个完整的程序，但它揭示了添加、删除和移动链表的机制：

#include <iostream>
using namespace std;

//class Data to store ages. in a real program this class can be any other
//class for example a student class or customer...
class Data
         {
         public:
               Data(int age):itsAge(age){}
               ~Data(){}
               void SetAge(int age){itsAge=age;}
               int  getAge()const{return itsAge;}
         private:
                int itsAge;
         };

//the most important part of the program is the linked0list
class Node
          {
          public:
                //we just make itsPtrHead when created points to Null even if we pass a pointer to Data that is not NULL
                Node(Data* pData): itsPtrData(pData),itsPtrHead(NULL),itsCount(0){}

                Data* getPdata()const;
                Node* getPnext()const;
                int   getCount()const{return itsCount;}

                void  insertNode(Data*);//import bcause it shoes the mechanism of linked-list
                void  deleteNode(int);//most significant in this program
                Data* findData(int&,int);
                void  print()const;
         private:
                Data* itsPtrData;
                Node* itsPtrHead;
                int   itsCount;

          };

Data* Node::getPdata()const
{
if(itsPtrData)
    return itsPtrData;
else
    return NULL;
}
Node* Node::getPnext()const
{
return itsPtrHead;
}
void Node::insertNode(Data* pData)
{
Node* pNode=new Node(pData);//create a node
Node* pCurrent=itsPtrHead;//current node which points first to the first node that is the "head bode"
Node* pNext=NULL;//the next node

int NewAge=pData->getAge();//the new age that is past to insertNode function
int NextAge=0;//next age
itsCount++;//incrementing the number of nodes

//first we check wether the head node "itsPtrHead" points NULL or not
//so if it is null then we assign it the new node "pNode" and return from insert function
if(!itsPtrHead)
    {
    itsPtrHead=pNode;
    return;
    }
//if the condition above fails (head is not null) then check its value and
//compare it with new age and if the new one is smaller than the head
//make this new one the head and then the original node that head points to it make it its next node to the head
if(itsPtrHead->getPdata()->getAge() > NewAge)
    {
    pNode->itsPtrHead=itsPtrHead;
    itsPtrHead=pNode;
    //exit the function
    return;
    }
//if the condition above fails than we move to the next node and so on
for(;;)
    {
    //if the next node to the current node is null the we set it with this new node(pNode) and exit
    if(!pCurrent->itsPtrHead)
        {
        pCurrent->itsPtrHead=pNode;
        return;
        }
    //else if it not null(next node to current node)
    //then we compare the next node and new node
    pNext=pCurrent->itsPtrHead;
    NextAge=pNext->getPdata()->getAge();
    //if next node's age is greater than new then we want new node 
    //to be the next node to current node then make the original next to current to be the next to its next
    if(NextAge > NewAge)
        {
        pCurrent->itsPtrHead=pNode;
        pNode->itsPtrHead=pNext;
        //exitting
        return;
        }
    //if no condition succeeds above then move to next node and continue until last node
    pCurrent=pNext;
    }
}
// delete a node is a bit different from inserting a node
void Node::deleteNode(int age)
{     
//deleting a node is much like adding one the differecne is a bit trickier
Node* pTmp=itsPtrHead;
Node* pCurrent=itsPtrHead;
Node* pNext=NULL;

//1 checking for wether age (node contains age) to be deleted does exist
for(;pTmp;pTmp=pTmp->itsPtrHead)
    {
    if(pTmp->getPdata()->getAge() == age)
        break;
    }
//if age to be deleted doesn't exist pop up a message and return
if(!pTmp)
    {
    cout<<age<<": Can't be found!\n";
    return;
    }

int NextAge=0;

for(;;)
    {
    //if age to be deleted is on the head node
    if(itsPtrHead->getPdata()->getAge() == age)
        {
        //store the next to head node
        pTmp=itsPtrHead->itsPtrHead;
        //delete head node
        delete itsPtrHead;
        //assign the head new node (node after the original head)
        itsPtrHead=pTmp;
        //decrement the count of nodes
        itsCount--;
        //exiting gracefully
        return;
        }
    //moving to next node
    pNext=pCurrent->itsPtrHead;
    NextAge=pNext->getPdata()->getAge();
    //checking next node age with age to be deleted. if they
    //match delete the next node
    if(NextAge == age)
        {
        //next node holds the target age so we want its NEXT node
        //and store it in pTmp;
        pTmp=pNext->itsPtrHead;//Next node of the target node
        //pCurrent doesn't yet hold the target age but it is the
        //previous node to target node
        //change the next node of pCurrent so that it doesn't
        //point to the target node but instead to the node right
        //after it
        pCurrent->itsPtrHead=pTmp;
        //delete the target node (holds the target age) 
        delete pNext;
        //decrement number of nodes
        itsCount--;
        //exit
        return;
        }
    //if pNext doesn't point to target node move to the next node
    //by making pCurrent points to the next node in the list
    pCurrent=pNext;
    }

}

void Node::print()const
{
Node* pTmp=itsPtrHead;
while(pTmp)
    {
    cout<<"age: "<<pTmp->getPdata()->getAge()<<endl;
    pTmp=pTmp->itsPtrHead;
    }
}
int main()
{
//note this is not a real proram just we show how things works

Data* pData=new Data(6);
Node theNode(pData);
theNode.print();
pData=new Data(19);
theNode.insertNode(pData);
pData=new Data(20);
theNode.insertNode(pData);
pData=new Data(23);
theNode.insertNode(pData);
pData=new Data(25);
theNode.insertNode(pData);
pData=new Data(30);
theNode.insertNode(pData);
pData=new Data(27);
theNode.insertNode(pData);
pData=new Data(33);
theNode.insertNode(pData);
pData=new Data(18);
theNode.insertNode(pData);

theNode.print();
cout<<endl<<endl;

//int age;
//int index;
//cout<<"Age to finde: ";
//cin>>age;
//cout<<endl;
//theNode.Find(index,age);

//cout<<age<<" : Found on index: "<<index<<endl; 

//theNode.modify(age);

//theNode.print();
int age;
cout<<"age to delete: ";
cin>>age;
cout<<endl;

theNode.deleteNode(age);
theNode.print();

cout<<endl<<endl<<endl;
return 0;
}
//modify and other member functions are not the purpose of this program