Deleting Node in Linked List C++

Question

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.

Answer 1

void Delete()
{
    int num;
    cout<<"enter node to delete"<<endl;
    cin>>num;
    node *nodeptr=head;
    node *prev;

    if(head==0)
    {   
        cout<<"list is empty"<<endl;
    }
    else if(head->data==num)
        {
          node *t=head;
          head=head->next;
          delete t; 
        }   
        else
        {
        nodeptr=head;
        prev=head;
        while(nodeptr!=NULL)
        {
            if(nodeptr->data==num)
            {
                prev->next=nodeptr->next;
                node *tem=nodeptr->next;
                delete tem;
            }
            prev=nodeptr;
            nodeptr=nodeptr->next;
        }
        }
}

Answer 2

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:

#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

Answer 3

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 entry to current for clarity

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.

Answer 4

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

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.

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.

Answer 5

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);
}