Assignment operator in linked list C++

Question

I'm trying to implement linked list in c++.

I implement my assignment operator like this:

// assignment operator
template<class T>
LinkedList<T>& LinkedList<T>::operator = (const LinkedList& rhs) {

if (&rhs != this) {
    Node *tmp = head;

    while (tmp -> next) {
        head = head -> next;
        delete tmp;
        tmp = head;
    }

    tmp = rhs -> head;

    while (tmp) {
        append(tmp);
        tmp = tmp -> next;
    }
}

    return *this;
}

In my main function, i use the following code to test:

LinkedList<int> *lst1 = new LinkedList<int>(7);

LinkedList<int> *lst2 = new LinkedList<int>(101);

std::cout << lst1 -> head -> data << std::endl;
std::cout << lst2 -> head -> data << std::endl;

lst1 = lst2;

std::cout << lst1 -> head -> data << std::endl;

delete lst1;
delete lst2;            <--------------- error here

As I expect, the console outputs:

7 101 101

But when the program try to delete lst2, i get an error saying:

pointer being freed was not allocated

I use debugger and find out when the program is doing assignment:

lst1 = lst2;

lst1 is actually referring to the address that points lst2 instead of getting a copy of lst2, so when i delete lst1, lst2 is already gone.

So can anyone please tell me what is wrong with my assignment operator?

I'm sorry if this is a novice question but I've been spending a few hours and could not figure out.

My completed code is shown below:

template<class T>
class LinkedList {

private:
    class Node {
    public:
        T data;
        Node *next;

        // default constructor
        Node() = default;

        // constructor with data
        Node(const T& data) : data(data), next(NULL) {}

    };

public:
    Node *head;

    LinkedList(const LinkedList& copyLst);
    LinkedList& operator=(const LinkedList& byValList);
    LinkedList() : head(NULL){}
    LinkedList(Node *newNode) : head(newNode) {}
    LinkedList(T val) {
        head = new Node(val);
    }
    ~LinkedList();

    static LinkedList<int> sumLists(const LinkedList<int>& lst1, const LinkedList<int>& lst2) ;

    void insertAtFront(T val);
    void insertAtEnd(T val);
    void printList();
    void insert(T val);

    void append(const Node&);
};

// copy constructor
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& copyLst) {

    const Node *cpCurrent = copyLst.head;
    Node *lsCurrent = NULL;

    if (cpCurrent != NULL) {
        head = new Node(cpCurrent -> data);
        lsCurrent = head;

        cpCurrent = cpCurrent -> next;

    }

    while (cpCurrent != NULL) {
        Node *newNode = new Node(cpCurrent -> data);
        lsCurrent -> next = newNode;

        lsCurrent = lsCurrent -> next;
        cpCurrent = cpCurrent -> next;
    }
}

// assignment operator
template<class T>
LinkedList<T>& LinkedList<T>::operator = (const LinkedList& rhs) {

    if (&rhs != this) {
        Node *tmp = head;

        while (tmp -> next) {
            head = head -> next;
            delete tmp;
            tmp = head;
        }

        tmp = rhs -> head;

        while (tmp) {
            append(tmp);
            tmp = tmp -> next;
        }
    }

    return *this;
}

// destructor
template<class T>
LinkedList<T>::~LinkedList() {
    Node *current = head;

    while (current != NULL) {
        head = head -> next;
        delete current;
        current = head;
    }
}

template<typename T>
void LinkedList<T>::append(const Node& node ){

    if (NULL == head) {
        Node *newNode = new Node(node -> data);
        head = newNode;
    } else {
        Node *current = head;

        while (current -> next) {
            current = current -> next;
        }


        Node *newNode = new Node(node -> data);
        current -> next = newNode;
    }
}

That isn't a constructor. It is an assignment *operator*. Both parties (the lhs and rhs) have already been constructed. And `lst1 = lst2;` isn't firing *any* of that code regardless. It is a simple assignment of one pointer to another, with the unfortunate side effect of leaking the very memory you just allocated for `lst1`. I.e., you're deleting the same list twice, and leaking the other. Why are you dynamically allocate *either* in the first place? — WhozCraig, Jun 16 '15 at 02:02
Also in your assignment operator you neglect to check whether `head` is NULL; if it is you get undefined behavior, and if it isn't you leak the last node. — Beta, Jun 16 '15 at 02:12
In addition to what Beta said about skipping the destination list's `head` node, you are also not iterating the destination list's nodes correctly when freeing them, either. The first loop should be more like this: `while (head) { Node *tmp = head->next; delete head; head = tmp; }` And your copy constructor is not initializing `head` if `copyLst.head` is NULL. — Remy Lebeau, Jun 16 '15 at 02:34
@RemyLebeau Do you mind telling me if I can use so-called copy-and-swap idiom in my assignment operator? should i use it for all the assignment operator? — 齐天大圣, Jun 16 '15 at 02:50
@Jackddddd `Do you mind telling me if I can use so-called copy-and-swap idiom` Does your copy constructor work? Does your destructor work? If both answers are "yes", then you can use copy / swap and ditch all of that code in your assignment operator. — PaulMcKenzie, Jun 16 '15 at 02:59
@Jackddddd: The source object passed to a **copy constructor** or **copy assignment operator** is usually (and supposed to be) `const`, so you cannot `swap` directly with it. But you can copy to a temp object, and then `swap` with the temp. That is not an uncommon implementation idiom. — Remy Lebeau, Jun 16 '15 at 03:10

score 7 · Accepted Answer · edited Jun 18 '16 at 00:20

Your current implementation duplicates code that already exists in the copy constructor, so why not reuse it?

If you have a working copy constructor and destructor, usage of the copy / swap idiom would be the easiest and safest way to implement the assignment operator.

#include <algorithm>
//...
template<class T>
LinkedList<T>& LinkedList<T>::operator = (const LinkedList<T>& rhs) 
{
    LinkedList<T> temp(rhs);
    std::swap(temp.head, head);
    return *this;
}

Given that your copy constructor and destructor work correctly, this is guaranteed to work correctly. We create a copy temp of the object rhs and swap out its contents with the contents of *this. When temp gets destroyed at the return, it takes along with it the old data that used to be in *this.

If you have a C++ 11 compiler, you can take advantage of move construction on the passed-in parameter with pass-by-value.

#include <algorithm>
//...
template<class T>
LinkedList<T>& LinkedList<T>::operator = (LinkedList<T> rhs) 
{
    std::swap(rhs.head, head);
    return *this;
}

* It should be noted that you need to swap ALL members of the class when using the copy and swap idiom, otherwise you will likely invalidate the class members' invariants *

It should be noted that copy-swap is not the most efficient implementation of either copy or move; its main benefit is ease of implementation. — M.M, Jun 16 '15 at 03:42
@M.M What would be the most efficient implementation of copying/moving a linked list then? — plasmacel, Jul 15 '17 at 17:10

Assignment operator in linked list C++

1 Answers1

Linked