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<typename T>
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<typename T>
struct DoubleLinkedList<T>::Node : DoubleLinkedList<T>
{
    T value;
    Node *prev;
    Node *next;

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

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

@Asphodel I didn't add anything, that is the point. The destructor crashes when the list is empty, because the logic in the destructor is all wrong, it should look more like this instead: ~DoubleLinkedList() { Node *tmp, *next; for (tmp = head; tmp != nullptr; tmp = next) { next = tmp->next; delete tmp; } } The print() itself is fine — Remy Lebeau
– Remy Lebeau, Commented Feb 2, 2022 at 19:46
Unrelated: DoubleLinkedList should also observe the Rule of Five so that it can be copied and moved without being damaged. — user4581301
– user4581301, Commented Feb 2, 2022 at 19:56
Thanks everybody for helping, really appreciate it. Will try not to make stupid mistakes like this anymore. — Asphodel
– Asphodel, Commented Feb 2, 2022 at 20:05

Remy Lebeau · Accepted Answer · 2022-02-02 20:00:41Z

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 <iostream>
using namespace std;
 
template<typename T>
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 << "\n";
    }

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

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

Online Demo

A M · Accepted Answer · 2022-02-05 14:42:26Z

Unrelated.

You have chosen the "naive" approach (all OK!) for a double linked list with an explicit "head" and "tail" pointer. This will mostly lead to not optimal code , because of the need of tons of comparisons with these pointers and assignments to it.

The standard implementation uses a sentinel, This is also a node, but with a special functionality. Basically, the next pointer of this sentinel node is the start of the real list and the previous pointer is the end of the list.

With that you can use standard functions in a more simple way. The main working horses are the "insert" and "erase" function. Most of the other stuff can be derived from that.

It is worth to examine that.

Please see below an example implementation (only partly tested and not fully complete), based on that design approach. I also added iterator functionality (even inefficient and non standard bidrectional and random access).

This may help you to get an idea for your future work and practising.

#include <iostream>
#include <iterator>
#include <vector>
#include <type_traits>
#include <initializer_list>
#include <algorithm>

// ------------------------------------------------------------------------------------------------
// This would be in a header file -----------------------------------------------------------------

// Type trait helper to identify iterators --------------------------------------------------------
template<typename T, typename = void> 
struct is_iterator { static constexpr bool value = false; };
template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
    static constexpr bool value = true;
};

// The List class ---------------------------------------------------------------------------------
template <typename T>
class List {
    // Sub class for a Node -----------
    struct Node {
        Node* next{};
        Node* previous{};
        T data{};
        Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
        Node(Node* const n, Node* const p) : next(n), previous(p) {}
        Node() {}
    };


    // Private list data and functions --------
    size_t numberOfElements{};
    Node* head{};
    void init() { head = new Node(); head->next = head; head->previous = head; numberOfElements = 0; }

public:
    struct iterator;    // Forward declaration

    // Constructor --------------------
    List() { init(); }
    explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
    explicit List(const size_t count) { init(); insert(begin(), count); }
    template <typename Iter>
    List(const Iter& first, const Iter& last) { init(); insert(begin(),first, last); }
    List(const List& other) { init(), insert(begin(), other.begin(), other.end()); };
    List(List&& other) : head(other.head), numberOfElements(other.numberOfElements) { other.init(); }
    List(const std::initializer_list<T>& il) { init(); insert(begin(), il.begin(), il.end()); }

    // Assignment ---------------------
    List& operator =(const List& other) { clear(); insert(begin(), other.begin(), other.end()); return *this; }
    List& operator =(List&& other) { clear(); head = other.head; numberOfElements = other.numberOfElements; other.init(); return *this; }
    List& operator =(const std::initializer_list<T>& il) { clear(); insert(begin(),il.begin(),il.end()); return *this; }

    void assign(const size_t count, const T& value) { clear(); insert(begin(), count, value); }
    template <typename Iter>
    void assign(const Iter& first, const Iter& last) { clear(); insert(begin(), first, last);}
    void assign(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); }
    

    // Destructor ---------------------
    ~List() { clear(); }

    // Element Access -----------------
    T& front() { return *begin(); }
    T& back() { return *(--end()); }

    // Iterators ----------------------
    iterator begin() const { return iterator(head->next, head); }
    iterator end() const { return iterator(head, head); }

    // Capacity -----------------------
    size_t size() const { return numberOfElements; }
    bool empty() { return size() == 0; }

    // Modifiers ----------------------
    void clear();

    iterator insert(const iterator& insertBeforePosition, const T& value);
    iterator insert(const iterator& insertBeforePosition);
    template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool> = true>
    iterator insert(const iterator& insertBeforePosition, const Iter& first, const Iter& last);
    iterator insert(const iterator& insertBeforePosition, const size_t& count, const T& value);
    iterator insert(const iterator& insertBeforePosition, const std::initializer_list<T>& il);

    iterator erase(const iterator& posToDelete);
    iterator erase(const iterator& first, const iterator& last);


    void push_back(const T& d) { insert(end(), d); }
    void pop_back() { erase(--end()); };

    void push_front(const T& d) { insert(begin(), d); }
    void pop_front() { erase(begin()); };

    void resize(size_t count);
    void resize(size_t count, const T& value);

    void swap(List& other) { std::swap(head, other.head); std::swap(numberOfElements, other.numberOfElements); }

     // Operations --------------------
    void reverse();

    // Non standard inefficient functions --------------------------
    T& operator[](const size_t index) const { return begin()[index]; }

    // ------------------------------------------------------------------------
    // Define iterator capability ---------------------------------------------
    struct iterator {

        // Definitions ----------------
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Data -----------------------
        Node* iter{};
        Node* head{};

        // Constructor ----------------
        iterator(Node*const node, Node* const h) : iter(node), head(h) {};
        iterator() {};

        // Dereferencing --------------
        reference operator*() const { return iter->data; }
        reference operator->() const { return &**this; }

        // Arithmetic operations ------
        iterator operator++() { if (iter != head) iter = iter->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++* this; return tmp; }
        iterator operator--() { if (iter != head->next) iter = iter->previous; return *this; }
        iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }

        iterator operator +(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)++temp; else while (k++)--temp; return temp;
        }
        iterator operator +=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)++* this; else while (k++)--* this; return *this;
        };
        iterator operator -(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k++)++temp; return temp;
        }
        iterator operator -=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k++)++* this; return *this;
        };
        // Comparison -----------------
        bool operator ==(const iterator& other) const { return iter == other.iter; };
        bool operator !=(const iterator& other) const { return iter != other.iter; };
        bool operator < (const iterator& other) const { return other.iter - iter < 0; };
        bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
        bool operator > (const iterator& other) const { return other.iter - iter > 0; };
        bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };

        // Special non standard functions -----------------
        difference_type operator-(const iterator& other) const;
        reference operator[] (const size_t index);
    };
};


// ------------------------------------------------------------------------------------------------
// Implementation of list functions. This would normally go into a TCC file -----------------------

// List class functions ---------------
template <typename T>
void List<T>::clear() {

    for (Node* nextNode{}, * currentNode(head->next); currentNode != head; currentNode = nextNode) {
        nextNode = currentNode->next;
        delete currentNode;
    }
    init();
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const T& value)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous, value);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
    ++numberOfElements;
    return iterator(newNode, head);
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
    ++numberOfElements;
    return iterator(newNode, head);
}

template <typename T>
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool>>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const Iter& first, const Iter& last) {
    iterator result(insertBeforePosition.iter, head);
    if (first != last) {
        result = insert(insertBeforePosition, *first);
        Iter i(first);
        for (++i; i != last; ++i)
            insert(insertBeforePosition, *i);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const size_t& count, const T& value) {

    iterator result(insertBeforePosition.iter, head);
    if (count != 0u) {
        result = insert(insertBeforePosition, value);
        for (size_t i{ 1u }; i < count; ++i)
            insert(insertBeforePosition, value);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const std::initializer_list<T>& il) {
    return insert(insertBeforePosition, il.begin(), il.end());
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& posToDelete) {

    iterator result = posToDelete;
    ++result;

    Node* nodeToDelete = posToDelete.iter;

    if (nodeToDelete != head) {

        nodeToDelete->previous->next = nodeToDelete->next;
        nodeToDelete->next->previous = nodeToDelete->previous;

        delete nodeToDelete;
        --numberOfElements;
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& first, const List<T>::iterator& last) {
    iterator result{ end() };
    if (first == begin() && last == end())
        clear();
    else {
        while (first != last)
            first = erase(first);
        result = last;
    }
    return result;
}

template <typename T>
void List<T>::resize(size_t count) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count; ++i)
            insert(end());
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::resize(size_t count, const T& value) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count; ++i)
            insert(end(),value);
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::reverse() {
    const Node* oldHead = head;

    for (Node* nptr = head; ; nptr = nptr->previous) {
        std::swap(nptr->next, nptr->previous);
        if (nptr->previous == oldHead) // Previous was the original next
            break;
    }
}

// ------------------------------------
// Iterator functions -----------------
template <typename T>
typename List<T>::iterator::difference_type List<T>::iterator::operator-(const iterator& other) const {

    difference_type result{};
    Node* nptr = head;

    int indexThis{ -1 }, indexOther{ -1 }, index{};

    do {
        nptr = nptr->next;
        if (nptr == iter)
            indexThis = index;
        if (nptr == other.iter)
            indexOther = index;
        ++index;
    } while (nptr != head);

    if (indexThis >= 0 and indexOther >= 0)
        result = indexThis - indexOther;
    return result;
}
template <typename T>
typename List<T>::iterator::reference List<T>::iterator::operator[] (const size_t index) {
    Node* nptr = head->next;
    for (size_t i{}; i < index and nptr != head; ++i, nptr = nptr->next)
        ;
    return nptr->data;
}

// ------------------------------------------------------------------------------------------------
// This would be in a cpp file --------------------------------------------------------------------
int main() {
    List<int> list{ 1,2,3,4,5 };

    std::cout << "Original List\n";
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    std::cout << "\nInternal reverse function. Kust swap ointers in Node\n";
    list.reverse();
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    // Sort it again
    std::cout << "\nSort it again (Values will be copied)\n";
    std::sort(list.begin(), list.end());
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    std::cout << "\nReverse function from algorithm library. Reverse values with copy\n";
    std::reverse(list.begin(), list.end());
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    // Use reverse iterators
    std::cout << "\nBuild and use reverse iterators\n";
    std::reverse_iterator<List<int>::iterator> riter = std::make_reverse_iterator(list.end());
    std::reverse_iterator<List<int>::iterator> riterEnd = std::make_reverse_iterator(list.begin());

    for (; riter != riterEnd; ++riter)
        std::cout << *riter << ' '; std::cout << '\n';

    return 0;
}

thanks for your suggestion, may I ask if it's common to use aggregate initialization in C++?
Yes, that is quite common. If you look in the CPP Reference (en.cppreference.com/w) then you will find many containers taking a std::initializer_list or direct aggregate initialization.

Collectives™ on Stack Overflow

Delete in Linked List

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related