CODEWITHSUNDEEP
c++
Jack F
Jack F

Reputation: 553

copy constructor for a linked list classes

So I want to copy a whole linked list classes, I have trouble figuring it out how to do so, 

class list{
   public:
  list(const list &t);
private:
  struct Node{
    int x;
    Node *next;
  }*p;

I started with something like this:

list::list(const list &t){
  Node* q;
  q=new Node;
  while (p!=NULL){
    q->x= p->x;}
}

but I'm not sure if I am on the right track or what. I also have trouble how should I test such a copy constructor? For example I have list l1, then i insert couple integers into a list and then how I can copy it?

Upvotes: 0

Views: 10172

Answers (3)

Denis Ermolin
Denis Ermolin

Reputation: 5556

In your example it never will work if you initialized p or will work forever if p != NULL. You must allocate new nodes while traversing through t list:

  p = NULL;
  Node* copy = l.p;
  Node* insert = p;
  Node* inserted_el = NULL;
  while (copy){
     insert = new Node(); 
     insert->x = copy->x; 
     insert->next = NULL;
     if (inserted_el) {
         inserted_el->next = insert; //copy memory pointer to next element
     } else {
         p = insert; //copy memory pointer to list head
     }
     copy = copy->next;
     inserted_el = insert;
  }

This is basic idea. Also don't forget to implement assign operator and destructor. Usage: 

list t1;
//insert nodes
list t2(t1);

Upvotes: 2

ozox
ozox

Reputation: 472

With your design of class, you need to be careful with memory management. This is the code:

list::list(const list& t) {
  Node* n = t.p;
  Node* m = p;
  while (n) {
    if (!m) {
      m = new Node(); // Allocate memory.
      if (!p) p = m;
    }
    m->x = n->x;
    m = m->next;
    n = n->next;
  }

  if (m) { // Original list is longer, delete the rest of the list.
    Node * tmp = m;
    m = m->next;
    delete tmp;
  }
}

Upvotes: 1

Kirill Kobelev
Kirill Kobelev

Reputation: 10557

The biggest trouble in your code is that you do not duplicate each node of the list while you need to do so.

Here is the code of the ctor:

list::list(const list &t)
{
  p = NULL;            // Init the head of the list this is vital important.

  // Loop over the elements of the passed list if any.
  Node *pt = t.p;
  Node *last_local_element = NULL;
  while (pt != NULL)
  {
     // Allocate a new node and set the fields there.
     Node *q = new Node;
     q->x= pt->x;
     q->next = NULL;

     // Add new node to the local list.
     if (last_local_element != NULL) {
         last_local_element->next = q;
     } else {
         p = q;
     }

     last_local_element = q;

     // Shift the loop variable along the passed list.
     pt = pt->next;
  }
}

There are 2 most often cases when the copy ctor is called:

list my_list1;

list my_list2(my_listl);           // Explicit call.
list my_list3 = my_listl;          // Assignment in the definition statement.

Upvotes: 1

Related Questions