patterncppMinor
Linked list with deep copy constructor
Viewed 0 times
withdeepconstructorlistlinkedcopy
Problem
I've created a linked list template class which contains a copy constructor that performs a deep copy of the list.
LinkedList.hpp
LinkedList.cpp
From what I can tell, the default copy constructor implements this functionality naturally, but I wanted to see if I could create a deep copy of a linked list myself using a self-defined copy constructor.
When I test this using:
It prints
LinkedList.hpp
template
class LinkedList {
protected:
struct Node {
T value;
Node *next;
Node(T val, Node *nxt=NULL) {
value = val;
next = nxt;
}
};
Node *head;
public:
LinkedList();
LinkedList(LinkedList &obj);
~LinkedList();
};LinkedList.cpp
template
LinkedList::LinkedList() {
head = NULL;
}
template
LinkedList::LinkedList(LinkedList &obj) {
if (obj.head == NULL) {
head = NULL;
}
else {
head = new Node(obj.head->value);
Node *current = head;
Node *objHead = obj.head;
Node *currentObj = objHead;
while (currentObj->next != NULL) {
current->next = new Node(currentObj->next->value);
currentObj = currentObj->next;
current = current->next;
}
}
}
template
LinkedList::~LinkedList() {
Node *current = head;
while (current != NULL) {
Node *garbage = current;
current = current->next;
delete garbage;
}
}
template class LinkedList;
template class LinkedList;
template class LinkedList;
template class LinkedList;From what I can tell, the default copy constructor implements this functionality naturally, but I wanted to see if I could create a deep copy of a linked list myself using a self-defined copy constructor.
When I test this using:
LinkedList ll;
ll.add(1);
ll.add(2);
ll.add(3);
ll.add(4);
LinkedList ll2 = ll;
ll.add(5);
ll.displayList();
ll2.displayList();It prints
1,2,3,4,5 and then 1,2,3,4. I believe this is correct. Are there any improvements I can make to the implementation of this?Solution
A few fairly obvious points:
Prefer
Unless you really need to support older compilers, you're generally better off using
Prefer member initializer lists over assignment in a constructor
The most obvious example here would be to replace your
...with one using a member initializer list:
Note that yes, in this case, although the parameter being used to initialize it have the same name, but the compiler can keep track of which is which anyway.
Rule of three/five/zero
Note that in virtually every case, if you provide a destructor and a copy ctor, you also want a copy assignment operator. If you want the better efficiency you can get from move construction/move assignment available in C++11 and later, you'll probably want to add overloads of those that accept rvalue references. I consider it open to debate whether the rule of zero really applies well in this case--I've written a linked list that used smart pointers, but I was never entirely happy with it. It's clumsy but workable in the case of a singly linked list. For a doubly linked list, it's...basically unmanageable.
Side Note
Contrary to your statement, if you don't include a copy ctor, you probably won't get correct results with this sort of class. In particular, the compiler will generate code that does a shallow copy, so only the head pointer in the LinkedList object will be copied. This means if you copy a linked list, you'll end up with both pointing to a single head node. In itself that's not necessarily a problem, but when either of those is destroyed, all the nodes in the list will be destroyed, so in essence you've just destroyed both linked lists, not just the one you intended to. Attempting to use or destroy the one that wasn't supposed to have been destroyed yet will give undefined behavior.
Prefer
nullptr over NULLUnless you really need to support older compilers, you're generally better off using
nullptr in new code. If you do use nullptr, you can still support older compilers if really necessary--it's basically just a class that provides conversions for pointer to T and pointer to member.Prefer member initializer lists over assignment in a constructor
The most obvious example here would be to replace your
node constructor:Node(T val, Node *nxt=NULL) {
value = val;
next = nxt;
}...with one using a member initializer list:
Node(T value, Node *next = nullptr) :
value(value),
next(next)
{}Note that yes, in this case, although the parameter being used to initialize it have the same name, but the compiler can keep track of which is which anyway.
Rule of three/five/zero
Note that in virtually every case, if you provide a destructor and a copy ctor, you also want a copy assignment operator. If you want the better efficiency you can get from move construction/move assignment available in C++11 and later, you'll probably want to add overloads of those that accept rvalue references. I consider it open to debate whether the rule of zero really applies well in this case--I've written a linked list that used smart pointers, but I was never entirely happy with it. It's clumsy but workable in the case of a singly linked list. For a doubly linked list, it's...basically unmanageable.
Side Note
Contrary to your statement, if you don't include a copy ctor, you probably won't get correct results with this sort of class. In particular, the compiler will generate code that does a shallow copy, so only the head pointer in the LinkedList object will be copied. This means if you copy a linked list, you'll end up with both pointing to a single head node. In itself that's not necessarily a problem, but when either of those is destroyed, all the nodes in the list will be destroyed, so in essence you've just destroyed both linked lists, not just the one you intended to. Attempting to use or destroy the one that wasn't supposed to have been destroyed yet will give undefined behavior.
Code Snippets
Node(T val, Node *nxt=NULL) {
value = val;
next = nxt;
}Node(T value, Node *next = nullptr) :
value(value),
next(next)
{}Context
StackExchange Code Review Q#121488, answer score: 2
Revisions (0)
No revisions yet.