CODEWITHSUNDEEP
c++linked-listcopy-constructor
StartingGroovy
StartingGroovy

Reputation: 2860

Looking for help when creating a copy constructor for a LinkedList class in C++

First, I realize that there are multiple topics about this on StackOverflow. I'm having a slight bit of trouble understanding the responses in some of them. I'm creating this in hopes that someone can help me understand the process.

I apologize if this question seems relatively novice, but I am doing my best to understand it.

I'm learning about data structures and have been asked to create a LinkedList implementation file based on a header that was provided.

This is homework, so please no 'here is the exact code' type answers. Pseudocode, steps, and hints are welcome.

Here is the part of the header that I'm working on at the moment:

typedef std::string ElementType;

class LinkedList
{
private:
   class Node
   {
   public:
      ElementType data;
      Node * next;

      Node( )
      : data( ElementType( ) ), next( NULL )
      { }

      Node( ElementType initData )
      : data( initData ), next( NULL )
      { }
   }; // end of Node class

   typedef Node * NodePointer;

public:
   LinkedList( );
   /* Construct a List object

      Precondition: none.
      Postcondition: An empty List object has been constructed.
   */

   LinkedList( const LinkedList &source );
   /* Construct a copy of a List object.

      Precondition: None. 
      Postcondition: A copy of source has been constructed.
   */

   ~LinkedList( );
   /* Destroys a List object.

      Precondition:  None.
      Postcondition: Any memory allocated to the List object has been freed.
   */

   const LinkedList & operator=( const LinkedList &rightSide );
   /* Assign a copy of a List object to the current object.


private:
   NodePointer first;
   int mySize;
};

So far, I've created the destructor, can you check and make sure it is correct?

//Destructor
LinkedList::~LinkedList() 
{ 
    NodePointer ptr = first;

    while(ptr != 0 ) {
        NodePointer next = ptr->next;
        delete ptr;
        ptr = next;
    }
    first = 0;
}

Now here is the part where I'm lost...What are the basic steps of creating the copy constructor? I've finished the default constructor which was simple, but I'm a bit confused with what I should be doing on the copy constructor.

I'm also slightly confused about overloading the = operator, I assume it will be very similar to the copy constructor.

Edit

My first attempt at the copy constructor:

LinkedList::LinkedList(const LinkedList & source)
{
    //create a ptr to our copy
    Node * copy_node = source.first;
    //where we will be inserting our copy
    Node * insert_node = first;

    while(copy_node != nullptr) 
    {
        //insert our new copy node
        insert_node = new Node(copy_node->data);
        //move to our next node
        copy_node = copy_node->next;

        if(copy_node != nullptr) {
            insert_node = insert_node->next;
        } else {
            insert_node = first;
        }

        //update size
        mySize++;

    }
}

I feel like something is missing there.

Upvotes: 3

Views: 3867

Answers (2)

dnk
dnk

Reputation: 661

The most easiest way is to implement a function which adds new nodes into the list and call it in the loop inside the constructor:

LinkedList(const LinkedList& rhs)
{
   Node* node = rhs.first;
   while (node) {
     add(node.data);
     node = node->next;
   }
}

void add(ElementType data)
{
   Node* node = new Node(data);
   // add node somehow
   // I'd recommend to keep pointer to the tail
}

Please note this implementation is not exception safe!

EDIT: added copy function for the copy constructor, the first step to the exception safety:

LinkedList(const LinkedList& rhs)
{
  copy(rhs.first, first);
}

void copy(Node* src, Node*& dest)
{
 // handle the head element separately
 if (!src) {
   return; // empty list
 } else {
   dest = new Node(src->data); // equivalent to first = new Node...
   src = src->next;
 }

 // copy the rest of the list
 Node* p = dest; 
 while (src) {
   p->next = new Node(src->data);
   src = src->next;
   p = p->next;
 }
}

Upvotes: 2

Jonathan Wakely
Jonathan Wakely

Reputation: 171263

What are the basic steps of creating the copy constructor? I've finished the default constructor which was simple, but I'm a bit confused with what I should be doing on the copy constructor.

Well, you need to copy the source, obviously. If the source is a list of N nodes then you need to construct another list of N nodes, with each node being a copy of the corresponding one in the source.

So loop over the source nodes and create copies of them.

I'm also slightly confused about overloading the = operator, I assume it will be very similar to the copy constructor.

Yes, except you need to dispose of the current nodes first. However, a simple and safe way to implement assignment is copy-and-swap, so define a correct swap member:

void swap(LinkedList& other)
{
   std::swap(first, other.first);
   std::swap(size, other.size);
}

Then use it to implement assignment:

LinkedList& operator=(const LinkedList& source)
{
   LinkedList(source).swap(*this);
   return *this;
}

This creates a temporary that is a copy of source, then swaps it with *this, so the old contents of *this get destroyed by the temporary, and *this ends up with the copied data.

N.B. the return type should be non-const, it is not idiomatic to return a const-reference from an assignment operator.

Upvotes: 3

Related Questions