Doubly Linked List Template Copy Constructor Assignment Operator
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;
}
Answer
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;
}
}