Search code examples
c++pointerslinked-listdynamic-memory-allocationdoubly-linked-list

Doubly Linked List in C++ (Pointer being freed was not allocated)


Can someone please tell me where I'm going wrong here? I believe the issue is with the clear() function but am not entirely sure. The goal is the create a doubly linked list. I still need to add some functionality, but feel that i've added enough to run what i've supplied in the main().

#include <iostream>
using namespace std;

template <class T>
class doubLList;

template <class T>
class doubNode{
    T data;
    doubNode<T>* next;
    doubNode<T>* prev;
public:
    doubNode(T data = T(), doubNode<T>* prev = nullptr, doubNode<T>* next = nullptr) : data(data),
    next(next), prev(prev) {}
    friend doubLList<T>;
    T& returnData() {return data;}
    doubNode<T>*& returnNext() {return next;}
};

template <class T>
class doubLList{
    doubNode<T>* head;
    doubNode<T>* tail;
public:
    doubLList() {head = new doubNode<T>; tail = new doubNode<T>; head->next = tail; tail->prev = head; cout<< "constructed" << endl;}
    doubLList(const doubLList<T>& copy);
    ~doubLList();
    doubLList<T>& operator=(const doubLList<T>& rhs);
    void clear();
    void insert(const T& data) {head->next = new doubNode<T>(data, head->next, head); head->next->next->prev = head->next;}
    doubNode<T>*& returnHead() {return head;}
};


template <class T>
void doubLList<T>::clear(){
    cout << "Clear" << endl;
    while(head->next != tail){
        cout << "Run" << endl;
        doubNode<T>* delNode = head->next;
        head->next = delNode->next;
        head->next->prev = head;
        delete delNode;
    }
}

template <class T>
doubLList<T>::doubLList(const doubLList<T>& copy){
    head = new doubNode<T>;
    tail = new doubNode<T>;
    head->next = tail;
    tail->prev = head;
    *this = copy;
}

template <class T>
doubLList<T>& doubLList<T>::operator=(const doubLList<T>& rhs) {
    if(this == &rhs){
        return *this;
    }
    clear();
    doubNode<T>* rhsPtr = rhs->next;
    while(rhs->next->next){
        tail->prev = new doubNode<T>(rhsPtr->data, tail, tail->prev);
        tail->prev->prev->next = tail->prev;
        rhsPtr = rhsPtr->next;
    }
}

template <class T>
doubLList<T>::~doubLList(){
    clear();
    delete head;
    delete tail;
    head = nullptr;
    tail = nullptr;
}



int main() {
    doubLList<int>test;

    cout << test.returnHead() << endl;

    test.insert(1);

    return 0;
}

Thanks in advance!


Solution

  • The following offered the correct implementation:

    Changed

    doubNode(T data = T(), doubNode<T>* prev = nullptr, doubNode<T>* next = nullptr) : data(data),
        next(next), prev(prev) {}
    

    to

    doubNode(T data = T(), doubNode<T>* next = nullptr, doubNode<T>* prev = nullptr) : data(data),
        next(next), prev(prev) {}