c++data-structureslinked-listnodescircular-list

I can´t delete a certain node in my linked list


I have the next linked list:

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

//Node class
class Node
{
public:
    string name;
    string age;

    Node *next;
    Node *prev;
    Node(string name, string age)
    {
        this->name = name;
        this->age = age;
        this->next = NULL;
        this->prev = NULL;
    }
};
//Doubly circular Linked list class
class List
{
private:
    Node *first;
    Node *last;

public:
    List()
    {
        this->first = NULL;
        this->last = NULL;
    }

    void deleteNode(string name)
    {

        Node *start = this->first;

        if (start == NULL)
        {
            return;
        }
        Node *curr = start, *prev_1 = NULL;
        while (curr->name != name)
        {
            if (curr->next == start)
            {
                printf("\nList doesn't have node with value = %d", name);
                return;
            }
            prev_1 = curr;
            curr = curr->next;
        }

        if (curr->next == start && prev_1 == NULL)
        {
            (start) = NULL;
            free(curr);
            return;
        }
        if (curr == start)
        {
            prev_1 = (start)->prev;
            start = (start)->next;
            prev_1->next = start;
            (start)->prev = prev_1;
            free(curr);
        }
        else if (curr->next == start)
        {
            prev_1->next = start;
            (start)->prev = prev_1;
            free(curr);
        }
        else
        {
            Node *temp = curr->next;
            prev_1->next = temp;
            temp->prev = prev_1;
            free(curr);
        }
    }

    void add(string name, string age)
    {
        Node *node = new Node(name, age);
        if (this->first == NULL)
        {
            this->first = node;
            this->first->next = node;
            this->first->prev = node;
            this->last = node;
        }
        else
        {
            this->last->next = node;
            node->next = this->first;
            node->prev = this->last;
            this->last = node;
            this->first->prev = this->last;
        }
    }

    void print()
    {
        Node *aux;
        aux = this->first;
        while (aux != NULL)
        {
            cout << aux->name << ", " << aux->age<<endl;
            aux = aux->next;
            if (aux == this->first)
            {
                break;
            }
        }
    }
};

int main(int argc, char const *argv[])
{
    List list;
    
    list.add("David", "25");
    list.add("James", "45");
    list.add("Charles", "78");
    list.add("Katty", "96");
    cout<<"List without delete any node"<<endl;
    list.print();
    //trying to delete a certain node
    list.deleteNode("David");
    cout<<"printing list without David because I deleted him above"<<endl;
    list.print();
    return 0;
}

In my function deleteNode I try to send a name to delete it from the linked list, but when in run my code it doesn't work, it only shows me the next:

List without delete any node
David, 25
James, 45
Charles, 78
Katty, 96

And my expected output would be:

List without delete any node
David, 25
James, 45
Charles, 78
Katty, 96
printing list without David because I deleted him above
James, 45
Charles, 78
Katty, 96

I don´t know what else to do, I hope you can help me, thanks.


Solution

  • Fors starters, free is the wrong way to free a pointer allocated with new. Use delete instead. Also, it's generally best to pass strings as const references.

    Your deleteNode function looks really complicated. Let me simplify it for you. Tell me what you think of this:

        void deleteNode(const string& name)
        {
    
            Node *start = this->first;
    
            while ((start != nullptr) && (start->name != name))
            {
               start = start->next;
            }
    
            if (start == nullptr)
            {
                return;
            }
    
            Node* prev = start->prev;
            Node* next = start->next;
    
            if (prev != nullptr)
            {
                prev->next = next;
            }
            else
            {
               first = next;
            }
    
            if (next != nullptr)
            {
                next->prev = prev;
            }
            else
            {
               last = prev;
            }
            delete start;
        }
    

    Likewise, add can be simplified to just:

        void add(const string& name, const string& age)
        {
            Node *node = new Node(name, age);
            
            if (this->last == NULL)   // first insert
            {
                first = node;
                last = node;
            }
            else
            {
                last->next = node;
                node->prev = last;
                last = node;
            }
        }