Doubly Linked List Template Copy Constructor Assignment Operator

Question

I wrote a simple implementation of doubly linked list in C++ using templates. However, I have some problems with copy constructor and assignment operator. My code gives me segmentation fault and I don't know how to fix it and where is the error (the problem is with copy constructor and assignment operator):

#include <iostream>
using namespace std;

template <class T>
class MyNode
{
public:
    MyNode(const T &e = T(), MyNode *n = NULL, MyNode *p = NULL) : element(e), next(n), previous(p) {}
    ~MyNode() {}
    T element;
    MyNode *next;
    MyNode *previous;

};

template <class T>
class MyList
{
private:
    MyNode<T> *head;
    MyNode<T> *tail;

public:
    MyList()
    {
        head = new MyNode<T>();
        tail = new MyNode<T>();
    }
    ~MyList()
    {
        clear();
        delete head;
        delete tail;
    }
    MyList(const MyList& otherList)
    {
        while (otherList.head->next!=NULL)
        {
            MyNode<T> *curr = otherList.head->next;
            insertLast(curr->element);
            otherList.head->next = curr->next;
        }
    }

    MyList& operator=(const MyList& otherList)
    {
        if(this == &otherList)
            return *this;

        while (otherList.head->next!=NULL)
        {
            MyNode<T> *curr = otherList.head->next;
            insertLast(curr->element);
            otherList.head->next = curr->next;
        }

        return *this;
    }

    bool isEmpty()
    {
        return (head->next == NULL);
    }

    void insertFirst(const T &e)
    {
        if (isEmpty())
        {
            MyNode<T> *newNode = new MyNode<T>(e);
            head->next = newNode;
            tail->previous = newNode;
        }
        else
        {
            MyNode<T> *actualFirst = head->next;
            MyNode<T> *newNode = new MyNode<T>(e, actualFirst);
            actualFirst->previous = newNode;
            head->next = newNode;
        }
    }
    void insertLast(const T &e)
    {
        if (isEmpty())
        {
            MyNode<T> *newNode = new MyNode<T>(e);
            head->next = newNode;
            tail->previous = newNode;
        }
        else
        {
            MyNode<T> *actualLast = tail->previous;
            MyNode<T> *newNode = new MyNode<T>(e, NULL, actualLast);
            actualLast->next = newNode;
            tail->previous = newNode;
        }
    }

    bool remove(MyNode<T> *r)
    {
        if (isEmpty())
        {
            return false;;
        }
        MyNode<T> *removeNode = tail->previous;
        while (removeNode!=NULL)
        {
            if (removeNode==r)
            {
                break;
            }
            removeNode = removeNode->previous;
        }
        if (removeNode==NULL)
        {
            return false;
        }
        else
        {
            MyNode<T> *afterRemove = removeNode->next;
            MyNode<T> *beforeRemove = removeNode->previous;
            if (afterRemove==NULL)
            {
                tail->previous = beforeRemove;
            }
            else
            {
                afterRemove->previous = beforeRemove;
            }
            if (beforeRemove==NULL)
            {
                head->next = afterRemove;
            }
            else
            {
                beforeRemove->next = afterRemove;
            }
            delete removeNode;
            return true;
        }
    }

    void clear()
    {
        while (tail->previous!=NULL)
        {
            MyNode<T> *remove = tail->previous;
            tail->previous = remove->previous;
            delete remove;
        }
    }

    void show()
    {
        while (head->next!=NULL)
        {
            MyNode<T> *curr = head->next;
            std::cout << curr->element << "\n";
            head->next = curr->next;
        }
    }

};

int main()
{
    MyList<int> l1;
    l1.insertLast(1);
    l1.insertLast(2);
    l1.insertLast(3);
    //l1.show();

    MyList<int> l2(l1);
    //l2 = l1;
    l2.show();

    return 0;
}

To find out the exact source of the error use the debugger to step through your code line by line. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jan 23, 2016 at 12:09

Rabbid76 · Accepted Answer · 2016-01-23 12:52:57Z

7

If you want to copy a list, you have to do a deep copy:

MyList(const MyList& otherList)
{
    if ( otherList.head == nullptr)
        head = tail = nullptr;                       // if "otherList" is empty the new list is empty too.
    else
    { 
        head = new MyNode<T>( otherList.head );      // allocate head and copy data
        MyNode<T> tempOther* = otherList.head->next;
        MyNode<T> temp* = head;
        while (tempOther != nullptr )
        {
            temp->next = new MyNode<T>( tempOther, nullptr, temp ); // allocate next elemnt and copy data ( predecessor is "temp" )
            temp = temp->next;                                      // temp refers to last element of list
            tempOther = tempOther->next;                            // step one forward
        }
        tail = temp;
    } 
}

The assigne operator works similar to the copy constructor.

Further you don't need to allocate a node for head and tail. headis only a pointer to the first element and tail is only a pointer to the last element of the list.

MyList()
  : head( nullptr )
  , tail( nullptr )
{}

Adapt isEmpty, insertFirst and insertLast like this:

bool isEmpty() { return head == nullptr); }

void insertFirst(const T &e)
{
    if (isEmpty())
        head = tail = new MyNode<T>(e);
    else
    {
        MyNode<T> *newNode = new MyNode<T>(e, head, nullptr );
        head->previous = newNode; // new node is predecessor of head
        head = newNode ;          // new head is new node
    }
}

void insertLast(const T &e)
{
    if (isEmpty())
        head = tail = new MyNode<T>(e);
    else
    {
        MyNode<T> *newNode = new MyNode<T>(e, nullptr, tail );
        tail->next = newNode; // new node is successor of tail
        tail = newNode ;      // new tail is new node
    }
}

Adapt method remove like this:

bool remove(MyNode<T> *r)
{
    MyNode<T> *removeNode = head;
    while ( removeNode != nullptr )    //  search the node to remove
    { 
        if ( removeNode == r )         // break if node to remove is found
           break;
        removeNode = removeNode->next; // setp on forward
    }
    if ( removeNode == r ) // if node was found remove it
    { 
        if ( removeNode == head )
            head = removeNode->next;     // if head is removed, new head is successor of head
        if ( removeNode == tail )
            tail = removeNode->previous; // if tail is removed, new tail is predecessor of tail
        if ( removeNode->previous!= nullptr )
            removeNode->previous->next = removeNode->next;      // new succesor of predecessor is successor
        if ( removeNode->next != nullptr )
            removeNode->next->previous = removeNode->previous;  // new prdecessor of successor is predecessor
        delete removeNode;
        return true;
    }
    return false;
}

Finally clear and show:

void clear()
{
    MyNode<T> *curr = head; 
    while ( curr != nullptr )
    {
        MyNode<T> *del = curr;
        curr = curr->next;
        delete del;
    }
    head = tail = nullptr; 
}

void show()
{
    MyNode<T> *curr = head; 
    while ( curr != nullptr )
    {
        std::cout << curr->element << "\n";
        curr  = curr->next;
    }
}

edited Jan 23, 2016 at 12:52

answered Jan 23, 2016 at 12:16

Rabbid76

212k30 gold badges163 silver badges205 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ziezi Over a year ago

Would it be better if (there was a remark indicating that) the class member functions were implemented in separate .cpp file from the .h file of the class interface?

Rabbid76 Over a year ago

@simplicisveritatis It's a template. You have to do it int the .h file.

Alex Over a year ago

For your copy constructor, shouldn't you have an if statement that prevents from self copy, something like this: if (this == &otherList) return *this?

Rabbid76 Over a year ago

@DynamicSquid You can do so, but in this case it is not necessary.

Collectives™ on Stack Overflow

Doubly Linked List Template Copy Constructor Assignment Operator

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related