Linked list and copy constructor

Question

I'm trying to write a basic, singly-linked list class in C++. I did it in my data structures class years back, but I can't remember the details.

Should my Node class have a copy constructor? It has a Node* as a member variable, and as far as I know you're always supposed to write a copy constructor, destructor, and assignment operator for classes that have dynamic members. But from what I've seen on the net, the List class takes care of the copying of Nodes. Is this really the case, and if so, why?

Answer 1

For a basic singly-linked list class, I'd recommend:

• After you allocate each node, don't move nor copy the node after it's allocated
• Therefore, disable the Node class copy contructor and assignment operator

C++ generates a default copy contructor and assignment operator if you don't define them. I recommend you disable these defaults, by declaring them as private and not implementing them.

---

But from what I've seen on the net, the List class takes care of the copying of Nodes. Is this really the case, and if so, why?

It takes care of copying nodes because it supports copying (making a copy of) the entire list (which means making a copy of every node in the list).

You don't need to support copying nodes, unless you support copying the whole list.

Answer 2

If you had a singly linked list :

A1 -> B1 -> C1

and your wrote your own copy constructor that, in turn calls the copy constructor on the internal Node* member, then you would get:

A1 -> B1 -> C1
A2 -> B2 -> C2

What you should not do is call the implicitly generated copy constructor which will not perform a cascading copy, what you will get is:

      A2
      |
      v
A1 -> B1 -> C1

So either write your own copy constructor to do a deep copy, or define an private copy constructor which implements a no-op.

BTW the std::list implements a doubly linked list and implements deep copy semantics.

Answer 3

You could do worse than copy the design of sgi's slist -- sgi's template library ("stl") was the basis for the part of the C++ standard library that's often still (not technically correctly;-) referred to as "stl". Unfortunately slist didn't make it (its doubly-linked cousin list OTOH did make it, and became std::list) but I do like it.

If you don't want to template the payload type and the allocator, it's fine to hard-code them, I guess; but the key point to retain is that "nodes" are an internal implementation detail -- you only expose the container type, with all the nice, canonical aspects (and of course the payload type must be known -- it's not hard to template it, btw;-), and you make "node" an opaque class in your .h (which just contains a class node;, and pointers to it in your class slist).