Delete node function in a linked list

Question

I have a program that is suppose to ask the user which item they wish to delete. The delete function should then successfully delete that node. I understand that I need to take the address from the previous node and make it point to the node after the node I am deleting and then delete the dangling node. I am having some difficulty understanding the syntax to get this to work. Here is my code. I have omitted the unnecessary functions.

#include <iostream> 
#include <cstddef> 
#include <string> 
using namespace std;

struct Node 
{
    string item; 
    int count; 
    Node *link; 
};

typedef Node* NodePtr;

void insert(NodePtr after_me, string an_item, int a_number); 
void list_remove(NodePtr& head, string an_item);
void head_insert(NodePtr& head, string an_item, int a_number); 
void show_list(NodePtr& head); 
NodePtr search(NodePtr head, string target);

int main() 
{ 
    string new_item, target, remove_item; 
    int new_count; 
    NodePtr head = NULL; 
    head_insert(head, "Tea", 2); 
    head_insert(head, "Jam", 3); 
    head_insert(head, "Rolls", 10);

    cout << "List contains:" << endl; 
    show_list(head);

    NodePtr after_me = head; 
    after_me = after_me ->link;
    cout << "Enter the item you wish to remove (string) \n"; 
    cin >> remove_item; 

    after_me = search(head, remove_item);

    if(after_me != NULL) 
    { 
        cout << "\nWill remove " << remove_item  << endl << endl;       

        list_remove(head, remove_item);

        cout << "List now contains:" << endl; 
        show_list(head); 
    }
    else 
    { 
        cout << "I can't find " << remove_item 
             << " in the list, so I can't remove anything \n"; 
    }

    system("PAUSE");
    return EXIT_SUCCESS; 
}

void list_remove(NodePtr& head, string remove_item)
{
    NodePtr remove_ptr; //pointer to the node that is being removed

    remove_ptr = search(head, remove_item); // finds the address for the item 
                                            // that is being removed and puts it
                                            // in remove_ptr


}

// Uses cstddef: 
void head_insert(NodePtr& head, string an_item, int a_number) 
{ 
    NodePtr temp_ptr; 
    temp_ptr = new Node;

    temp_ptr -> item = an_item; 
    temp_ptr -> count = a_number;

    temp_ptr->link = head; 
    head = temp_ptr; 
}

//Uses iostream and cstddef: 
void show_list(NodePtr& head) 
{ 
    NodePtr here = head;

    while (here != NULL) 
    { 
        cout << here-> item << "\t"; 
        cout << here-> count << endl; 
        here = here->link; 
    } 
}

NodePtr search(NodePtr head, string target) 
{ 
    // Point to the head node
    NodePtr here = head;

    // If the list is empty nothing to search 
    if (here == NULL) 
    { 
         return NULL; 
    }
    // Search for the item 
    else 
    { 
         // while you have still items and you haven't found the target yet 
         while (here-> item != target && here->link != NULL) 
             here = here->link;

         // Found the target, return the pointer at that location 
         if (here-> item == target) 
             return here;
         // Search unsuccessful, return Null 
         else 
             return NULL; 
    } 
}

I am unsure what I should add to the delete function to make it work. The syntax is confusing. — user2837034
– user2837034, Commented Oct 22, 2013 at 18:54
Clarify which 'syntax' in particular confuses you, instead of throwing all your code to us! — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Oct 22, 2013 at 18:56
BTW: Do you have the option to make this a double linked list, which would make insertion and removing easier? — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Oct 22, 2013 at 18:59
Another point: Improve code formatting! I have edited just some basics ... — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Oct 22, 2013 at 19:01

FlyCodeRepeat · Accepted Answer · 2013-10-22 20:17:59Z

2

To delete, you're going to need the node BEFORE the one to be deleted as well. The steps are:

// find the preceding_ptr
NodePtr preceding_ptr = head;
while(preceding_ptr != NULL && preceding_ptr->link != remove_ptr){
    preceding_ptr = preceding_ptr->link;
}

// now preceding_ptr is set, make it skip remove_ptr
preceding_ptr->link = remove_ptr->link;

// free up memory from remove_ptr

answered Oct 22, 2013 at 20:17

FlyCodeRepeat

3961 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

FlyCodeRepeat Over a year ago

FYI, this is the body of your list_remove method.

πάντα ῥεῖ · Accepted Answer · 2013-10-22 20:53:30Z

So, since you're not really showing what your going to try, I can't really tell which 'syntax' confuses you in particular. Just a guess ...

If I understand correctly it boils down to you want to know how to find the item placed just before the item you want to remove to manipulate it as necessary, right?
Just iterate through the list yourself then, instead of using the search() method:

void list_remove(NodePtr& head, string remove_item)
{
    NodePtr remove_ptr; //pointer to the node that is being removed

    remove_ptr = search(head, remove_item);
    if(remove_ptr != NULL) // indicates the item is part of the list and 
                           // we can remove it    
    {
         NodePtr predecessorNode = NULL;
         // Iterate the list to find the predecessor of remove_ptr
         for(NodePtr curNode = head; curNode != NULL; curNode = curNode->link)
         {
             if(curNode->link == remove_ptr) // Indicates that curNode is the
                                             // predecessor of remove_ptr
             {
                 predecessorNode = curNode;  // store it and ...
                 break;                      // ... exit the loop
             }
         }

         if(predecessorNode != NULL) // We have found a predecessor
         {
             // Now you have the predecessor for remove_ptr, 
             // manipulate it as necessary
         }
         else // indicates the item to remove is the head of the list
         {
             // You might need to manipulate head, depending on how your 
             // linked list is organized (set to remove_ptr->link most likely)
         }
    }
}

Collectives™ on Stack Overflow

Delete node function in a linked list

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related