Delete in Linked List

Question

So I revisited double linked list, found I'm really stupid, and can't figure things out even when I narrowed down problem to delete operator. I'm still playing around with templates, so maybe there's something wrong with templates as well. Print works fine without deleting a node. Please tell me what's wrong.

Result of code run is just that it doesn't print anything.

template
class DoubleLinkedList
{
    struct Node;
    Node *head;
    Node *tail;
public:
    DoubleLinkedList(Node *head = nullptr) : head(head) {
        if (head == nullptr) {
            tail = nullptr;
            return;
        }
        Node *tmp;
        for (tmp = head; tmp->next != nullptr; tmp = tmp->next);
        tail = tmp;
    }

    void addfront(T val) {
        Node *newnode = new Node(val, head);
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        newnode->next = head;
        head->prev = newnode;
        head = newnode;
    }
    void addend(T val) {
        Node *newnode = new Node(val, nullptr, tail); 
        // There's probably a very obvious reason here, but my brain is busted and can't figure out 
        // what's wrong 
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        tail->next = newnode;
        newnode->prev = tail;
        tail = newnode;
        
    }

    void del(T val) {
    
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next) {
            if (tmp->value == val) {
                if (tmp != head)
                    tmp->prev->next = tmp->next;
                else 
                    head = tmp->next;
                if (tmp->next != nullptr)
                    tmp->next->prev = tmp->prev;
                else
                    tail = tmp->prev;
                // print();
                delete tmp;  // delete not working, even when delete function is empty with just 
                             // delete head, it's a memory issue that my head can't wrap around
                break;
            }
        }
    }
    void print()
    {
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next)
            std::cout << tmp->value << ", ";
    }
    ~DoubleLinkedList() {
        Node *tmp;
        for (tmp = head; tmp->next != nullptr; tmp = tmp->next) 
            delete tmp->prev;
        delete tmp->prev;
        delete tmp;
    }
};

template
struct DoubleLinkedList::Node : DoubleLinkedList
{
    T value;
    Node *prev;
    Node *next;

    Node(T val, Node *next = nullptr, Node *prev = nullptr) : 
    value(val), prev(prev), next(next) {}
};

int main()
{
    DoubleLinkedList numlist;
    for (int i = 0; i < 10; i++)
        numlist.addend(i);
    numlist.del(0);
    numlist.print();
}

Remy Lebeau · Accepted Answer

The ~DoubleLinkedList() logic is all wrong. When the list is empty, head is nullptr, so accessing tmp->next in the loop is undefined behavior. And the way you are deleting nodes is just weird in general. It should look more like this instead:

~DoubleLinkedList() {
    Node *tmp, *next;
    for (tmp = head; tmp != nullptr; tmp = next) {
        next = tmp->next;
        delete tmp;
    }
}

The reason this was causing problems is because you have DoubleLinkedList::Node deriving from DoubleLinkedList, so delete'ing a node was calling the invalid ~DoubleLinkedList() destructor. There is no good reason for Node to derive from DoubleLinkedList at all.

After fixing those 2 things, the rest of the code works fine for me, especially the del() call:

#include 
using namespace std;
 
template
class DoubleLinkedList
{
    struct Node
    {
        T value;
        Node *prev;
        Node *next;

        Node(T val, Node *next = nullptr, Node *prev = nullptr) : 
            value(val), prev(prev), next(next) {}
    };

    Node *head;
    Node *tail;
public:
    DoubleLinkedList(Node *head = nullptr) : head(head) {
        if (head == nullptr) {
            tail = nullptr;
            return;
        }
        Node *tmp;
        for (tmp = head; tmp->next != nullptr; tmp = tmp->next);
        tail = tmp;
    }
 
    void addfront(T val) {
        Node *newnode = new Node(val, head);
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        newnode->next = head;
        head->prev = newnode;
        head = newnode;
    }
 
    void addend(T val) {
        Node *newnode = new Node(val, nullptr, tail); 
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        tail->next = newnode;
        newnode->prev = tail;
        tail = newnode;
    }

    void del(T val) {
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next) {
            if (tmp->value == val) {
                if (tmp != head)
                    tmp->prev->next = tmp->next;
                else 
                    head = tmp->next;
                if (tmp->next != nullptr)
                    tmp->next->prev = tmp->prev;
                else
                    tail = tmp->prev;
                // print();
                delete tmp;
                break;
            }
        }
    }

    void print()
    {
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next)
            std::cout << tmp->value << ", ";
        std::cout << "
";
    }

    ~DoubleLinkedList() {
        Node *tmp, *next;
        for (tmp = head; tmp != nullptr; tmp = next) {
            next = tmp->next;
            delete tmp;
        }
    }
};

int main()
{
    DoubleLinkedList numlist;
    for (int i = 0; i < 10; i++)
        numlist.addend(i);
    numlist.print();
    numlist.del(0);
    numlist.print();
}

Online Demo

Delete in Linked List

Answers (2)

Related Questions