operator= overload for Linked List issues

Question

I'm having issues with my implementation of the overloaded = operator for a linked list. The List class contains a Node* head pointer and a struct Node containing T* data and Node* next, where T is a template typename. I'm having trouble with what is happening at the end of the operator function where the destructor (in this case handled by makeEmpty) is being called twice by the end of the operator, once after iterating through the list and creating a new list of the same nodes and once after the operator function exits.

Here is the makeEmpty implementation:

// Does the work of the Destructor
template <typename T>
void List<T>::makeEmpty() {

cout << endl << endl << "DESTRUCTOR CALLED" << endl << endl;
List<T>::Node* tempPtr = head;

if (head != NULL) {

    List<T>::Node* nextPtr = head->next;

    for(;;) {
        if (tempPtr != NULL) {

            delete tempPtr->data;
            tempPtr = nextPtr;

            if (nextPtr != NULL)
                nextPtr = nextPtr->next;

            /*tempPtr = head->next;
            delete head;
            head = tempPtr;*/
        }

        else break;
    }
}

}

Here is the operator= overload implementation:

// Overloaded to be able to assign one list to another
template <typename T>
List<T> List<T>::operator=(const List& listToCopy) {

List<T> listToReturn;
listToReturn.head = NULL;
List<T>::Node* copyPtr = listToCopy.head;

List<T>::Node* thisPtr = head;

if (copyPtr != NULL && thisPtr != NULL) {
    for(;;) {
        if (copyPtr != NULL) {

            T* toInsert = new T(*copyPtr->data);
            listToReturn.insert(toInsert);

            copyPtr = copyPtr->next;
        }

        else{cout << endl << listToReturn << endl << endl; return listToReturn;}
    }
}
// if right-hand list is NULL, return an empty list
return listToReturn;
}

I've been debugging for a little bit and it seems that the second time the destructor is called, the head of the list being destroyed contains unreadable memory. I'm not even sure why the destructor is being called twice within the operator since the only list that needs to be destroyed is the listToReturn after it has been returned. (maybe my logic is flawed somewhere... I've just been thinking about this for too long)

If you guys need anymore info about the code, I'd be glad to provide. As usual, this is for an assignment, so I'm only asking for tips that may help me get in the right direction. So thanks to everyone for looking and helping!

Answer 1

You asked for pointers and tips, so I'm giving it:

1) Unnecessary dynamic data member

Your List<T>::Node does not need a dynamic member for the underlying data value. It should be constructible from a const T& and if implementing a C++11-compliant move-construction idiom, a T&& as well. And both should initialize the next member to nullptr

2) Copy-constructor for List<T> is mandetory

In accordance with the Rules of Three, Four, or Five, your class has dynamic members, and as such must properly manage them in a copy-construction and assignment operator action (or hide said implementations, but clearly that isn't an option for you, as it is part of your assignment).

3) Utilize the class copy-constructor for the assignment operator overload

Overloading an assignment operator where dynamic allocations are involved (and they are here, as your linked list of Node mandates it) should ideally utilize the copy-constructor and the copy/swap idiom for lifetime management. This has a number of benefits, the two most important being potentially eliding the copy-operation by an optimizing compiler, and exception safety that maintains objects in their original state.

4) The List<T>::operator = override should return a reference to the current object

The current object being assigned-to (the left side of the operator) should be a by-reference return result. It should be the object that is modified. This is part and parcel with the standard implementation for such an operator. You return a copy, but the original object remains untouched, thereby utterly defeating the purpose of the assignment operator (i.e. the lvalue side isn't actually modified in your implementation at all)

Each of these is addressed in detail below:

---

Unnecessary dynamic data member

As it is not posted, I must be somewhat soothsaying in what List looks like. I imagine something like this:

template<class T>
class List
{
private:
    struct Node
    {
        T* data;
        Node* next;
    };
    Node *head;

    // other members and decls...
};

With this your insertion and copy operations are having to take significant advantages to manage dynamic allocations of T objects where they shouldn't need to. List<T> should certainly own a chain of Node; but Node should own the actual T object, and be responsible for managing it therein; not List<T>. Consider this instead:

template<class T>
class List
{
private:
    struct Node
    {
        T data;
        Node* next;

        Node(const T& arg) 
            : data(arg), next()
        {}

        Node(const Node& arg)
            : data(arg.data), next()
        {}

    private:
        // should never be called, and therefore hidden. A
        // C++11 compliant toolchain can use the `delete` declarator.
        Node& operator =(const Node&);
    };
    Node *head;

    // other members and decls...
};

Now when a new node is needed to hold a T object (such as in an insertion operation) the following can be done:

template<typename T>
void List<T>::someFunction(const T& obj)
{ 
    Node *p = new Node(obj);
    // ...use p somewhere...
}

---

Copy-constructor for List<T> is mandetory

Your linked list, by its very nature, manages a dynamic chain. Therefore this class must implement copy-construction and assignment operations, the latter being part of your assignment and the reason you posted your question. Duplicating a linked list is fairly straight-forward, but some, for whatever reason, make it harder than it seems. The following is one of my preferred ways of doing it:

template<typename T>
List<T>::List(const List<T>& arg)
    : head()
{
    Node **dst = &head;
    const Node* src = arg.head;
    while (src)
    {
        *dst = new Node(*src);     // invoke Node copy-construction
        dst = &(*dst)->next;       // move target to new node's next pointer
        src = src->next;           // advance source
    }
}

This uses a simple technique of a pointer-to-pointer to hold the address of the pointer being populated with the next new node. Initially it holds the address of our head pointer. With each new node added it is advanced to hold the address of the newly added node's next member. Since Node(const Node&) already sets next to nullptr (see prior section) our list is always terminated properly.

---

Utilize the class copy-constructor for the assignment operator overload

The List<T>::operator = override should return a reference to the current object

Once we have a solid copy constructor, we can use it for overriding our assignment operator. This is done in a not-so-apparent way, but I'll explain after the code:

template<typename T>
List<T>& List<T>::operator=(List<T> byval)
{
    std::swap(head, byval.head); // we get his list; he gets ours
    return *this;
}

I'm sure you're looking at this and thinking, "Huh??". It deserves some explanation. Look carefully at the parameter byval being passed in, and consider why I named it as I did. It is not a traditional const reference you're likely used to seeing. It is value copy of the right-hand-side of the assignment expression. Thus, to create it the compiler will generate a new List<T>, invoking the copy-constructor to do so. The result of that copy is the temporary object byval we have as our parameter. All we do is exchange head pointers. Think about what that does. By exchanging head pointers we take his list and he takes ours. But his was a copy of the original right-side of the assignment expression, and ours, well, we want it deleted. And that is exactly what will happen when the destructor for byval is fired once this function is finished.

In short it makes code like this:

List<int> lst1, lst2;
lst1.insert(1);
lst2.insert(2);
lst1 = lst2; // <== this line

execute our function on the marked line. That function will make a copy of lst2, passing it into the assignment operator where lst1 will exchange head pointers with the temporary copy. The result will be lst1's old node will be cleaned up by the destructor of byval, and the new node list is properly in place.

There are a number of reasons to do this. First, it makes your assignment operator exception-safe. If an exception is tossed (usually a memory allocation exception, but it doesn't matter) no memory is leaked, and the original object lst1 remains in its original state. Second, the compiler can elide this away entirely if it chooses and the conditions are correct.

Anyway, these are some ideas and some points of bugs in your implementation. I hope you find them useful.