Deleting a specific node in Linked List C++

Question

I have a Student class which holds student data and my node is then made up of an object of this student class.

I would like to delete students with marks less then 550.I have a long list of students but the program deletes all data after finding out the first person with less marks.

Here is my linked List:

class LinkList // Linked List 
{
    struct Node // structure for Node containing Object of Student class
    {
        Student info;
        Node* link;
    };
    Node* head;
    
public:
    
    LinkList() // default constructor
    {
        head = NULL;
    }
    
    void CreateEntry();
    void print();
    void Delete();

};

Here is a sample of my data: (One line is each node)

S#  Roll_no     Name         marks
1   0777    Sherlock Holmes  777       
2   0789    John Watson      734       
3   0860    James moriarty   390       
4   0884    Irene Adler      732      
5   1003    Mycroft Holmes   410 
6   1004    Lord Blackwood   632

Here is my delete function:

Node* ptr = head;
    int n;
    
    while(ptr->link != NULL) // traversing to last element
    {
        n = ptr->info.GetSerialNo(); // where n becomes the total number of elements
        ptr = ptr->link;
    }

    Node* temp = head;
    for(int i=0; i<n; i++)
    {
        if(temp->info.Getmarks() < 550) // Getmarks returns the marks
        {
            if(temp != NULL && temp->link != NULL)
            {
                Node* nodeToDelete = temp->link;
                temp->link = temp->link->link;
                delete nodeToDelete;
            }   
        }
        else
        {
            temp = temp->link;
        }
    }
}

And the output I get is:

S#  Roll_no     Name         marks
1   0777    Sherlock Holmes  777       
2   0789    John Watson      734

Run your program under a debugger, put a breakpoint on the line with `Node* nodeToDelete = temp->link;`. Take note of the `temp` variable's contents. Now step until you reach the start of the next iteration. What is the value of `temp` now? What happens? More importantly, what did you expect to happen and why doesn't it? — Botje, Jul 22 '21 at 15:37
Unrelated: `while(ptr->link != NULL)` dies a horrible death if the list is empty because `ptr` will be `NULL`. Fix that and you'll find the function only works properly the first time you remove nodes. After that the serial number may not accurately represent the number of nodes in the list. That said, why not, do the search and removal in that initial loop? Search until there are no more nodes in the list. That'll always work. — user4581301, Jul 22 '21 at 15:39
Unrelated: your `temp != NULL` check is useless (you already accessed temp above) and your compiler probably removed the check. It should have warned you about this if your warning level is high enough. — Botje, Jul 22 '21 at 15:39
See the [Community Addition of this answer](https://stackoverflow.com/a/22122095/4581301) for a cleaner way to remove nodes from a singly linked list. — user4581301, Jul 22 '21 at 15:42
Unrelated: you assign the serial numbers to `n` in order to get the length of the list, yet you allow deletion. This could mean that your final `n` is greater or less than the length of your list. Why even use `n` at all? You could rewrite your `for` loop to `for(Node *ptr = head; ptr != NULL; ptr = ptr -> link)` which does all your checks for you — Guy Marino, Jul 22 '21 at 15:43
TOTALLY unrelated: how on earth did Sherlock outscore his older, smarter brother by so much? — user4581301, Jul 22 '21 at 15:44
Related: you are deleting *next* node instead of the current one. You should delete `temp`, not `temp->link`, and also reassign `temp` to `temp->link` for the next loop iteration. But to delete temp you also have to keep in mind the one who precedes `temp`, to be able to relink items properly. And if head item should be deleted, then you have to reassign `head` (but see the mentioned Community Addition about that). — Dialecticus, Jul 22 '21 at 15:49
You should really search the internet for "c++ delete node linked list". There are already a plethora of these questions on StackOverflow. — Thomas Matthews, Jul 22 '21 at 17:07

score 0 · Answer 1 · answered Jul 22 '21 at 19:31

I would like to delete students with marks less then 550

Your Delete() is way more complicated than it needs to be for that task. Also, it has some logic mistakes in it anyway.

Try something more like this instead:

void LinkList::Delete()
{
    Node* ptr = head;
    Node* previous = NULL;
    
    while (ptr != NULL)
    {
        Node* nextNode = ptr->link;

        if (ptr->info.Getmarks() < 550)
        {
            if (previous)
                previous->link = nextNode;

            if (head == ptr)
                head = nextNode;

            delete ptr;
        }
        else
            previous = ptr;

        ptr = nextNode;
    }
}

Alternatively:

void LinkList::Delete()
{
    Node* ptr = head;
    Node** previous = &head;
    
    while (ptr != NULL)
    {
        Node* nextNode = ptr->link;

        if (ptr->info.Getmarks() < 550)
        {
            *previous = nextNode;
            delete ptr;
        }
        else
            previous = &(ptr->next);

        ptr = nextNode;
    }
}

That being said, you really should use the standard std::list container instead of making your own linked list, then you can do this:

#include <list>

class LinkList // Linked List 
{
    std::list<Student> students;
    
public:
    
    LinkList() = default; // default constructor
    
    ...
    void Delete();

};

#include <algorithm>

void LinkList::Delete()
{
    students.erase(
        std::remove_if(students.begin(), students.end(),
            [](Student &s){ return s.Getmarks() < 550; }
        ),
        students.end()
    );
}

Deleting a specific node in Linked List C++

1 Answers1