Kevin Swagger Kevin Swagger - 1 month ago 18
C++ Question

Doubly Linked List Big Three

I am having a lot of trouble trying to get my copy constructor, destructor, and assignment operator working for a double linked list.
I have a class called dlist and a node class. The Node class contains a private node of next and previous and a data field. I am really stuck and I just can not for the life of me understand how to get these to work. If someone even just points out what's wrong. Sometimes I get a seg fault and other times I get a backtrace, depending on what I change in the big three.

//Destructor
template<class T>
dlist<T>::~dlist(){
node<T> *rmptr = head;
while(head != NULL && head != tail){
head = head -> next();
delete rmptr;
}
}

//Copy Constructor
template <class T>
dlist<T>::dlist(const dlist<T>& other)
{
if(other.head == NULL){
head = new node<T>;
tail -> set_next(head);
}
else{
head = new node<T>(other.head -> data());
tail = new node<T>;
head -> set_next(tail);
tail -> set_previous(head);
node<T> *source = other.head -> next();
node<T> *destination = head;
while(source != NULL && source != other.tail){
tail -> set_next(new node<T>);
destination -> set_next(tail);
tail -> set_data(source -> data());
tail = tail -> next();
source = source -> next();
}
}

}

//Assignment Operator
template<class T>
dlist<T>& dlist<T>::operator =(const dlist& other){

if(this == &other){
return *this;
}
node<T> * rmptr;
while(head != NULL){
rmptr = head;
head = head -> next();
delete rmptr;
}
head = tail = NULL;

node<T> *source, *destination;
if(other.head != NULL){
head = new node<T>(other.head -> data());
tail = new node<T>;
head -> set_next(tail);
tail -> set_previous(head);
node<T> *source = other.head -> next();
node<T> *destination = head;
while(source != NULL && source != other.tail){
tail -> set_next(new node<T>);
destination -> set_next(tail);
tail -> set_data(source -> data());
tail = tail -> next();
source = source -> next();
}
}

return *this;
}

Answer

This copy/assignment/constructor/destructor pattern is a classic (at least by my standards :))

  • First, you have to set head and tail to NULL (or nullptr) to avoid segfaults if objects are just created and unused. That avoids that destructor reads an uninitialized head. NULL prevents the destructor from doing something harmful
  • Second: create a destroy utility method used by the destructor (of course) and also by the assignment operator to free assigned object (else you get memory leaks). No need to copy/paste the same code. And I was first assuming that your deletion code was ok, but it's not.

destroy would look like this (fixed the the help of WhozCraig comment):

template<class T>
void dlist<T>::destroy()
{
    node<T> *rmptr;
    while(head != NULL && head != tail){
        rmptr = head;
        head = head -> next();
        delete rmptr;

    }
    head = tail = NULL; // set head to NULL again

}

destructor just looks like this:

template<class T>
dlist<T>::~dlist(){
   destroy();
} 
  • Third create a copy utility method used by the copy constructor and the assignment operator (they share a lot of identical code, no need to copy/paste)

The copy method looks like this:

template <class T>
void dlist<T>::copy(const dlist<T>& other)
{
    if(other.head == NULL){
        head = new node<T>;
        tail -> set_next(head);
    }
    else{
        head = new node<T>(other.head -> data());
        tail = new node<T>;
        head -> set_next(tail);
        tail -> set_previous(head);
        node<T> *source = other.head -> next();
        node<T> *destination = head;
        while(source != NULL && source != other.tail){
            tail -> set_next(new node<T>);
            destination -> set_next(tail);
            tail -> set_data(source -> data());
            tail = tail -> next();
            source = source -> next();
        }
    }

}

You can now implement your copy constructor & assignment operator very simply:

template<class T>
dlist<T>::dlist(const dlist<T>& other)
{
    copy(other);
}

//Assignment Operator
template<class T>
dlist<T>& dlist<T>::operator =(const dlist& other){

    if(this == &other){
        return *this;
    }
    destroy();
    copy(other);

    return *this;
}

You won't have any memory leaks when assigning an object into another already "full" (aka allocated) object, and you won't get a segfault from freeing unallocated area because on a new object head and tail are NULL.

I apologize for answering "beyond" the question, but this pattern is very useful, and untrained coders who attempt to code low-level classes like this always stumble on the same memory-leak/crash/copy-paste hurdles.

Comments