Copying a linked list- crashes the program

I have the following C code to copy a linked list(taken from Stanford CS Library files):

struct Node* CopyList(struct Node* head)
{
       struct Node* current = head;
       struct Node* newList= NULL;
       struct Node* tail= NULL;

       while (current !=NULL)
       {
             if(newList==NULL)
             {
                 newList=malloc(sizeof(struct Node));
                 newList->data=current->data;
                 newList->next=NULL;
                 tail= newList;
             }
             else
             {
                 tail= malloc(sizeof(struct Node));
                 tail= tail->next;
                 tail->data=current->data;
                 tail->next = NULL;
             }
 开发者_JS百科            current= current->next;
       }
       return(newList);
}

I have the following as a part of my main function:

struct Node* head = NULL;
for (i=3; i >=1;i--)   //insert 3 elements into the linked list
   {                   //push inserts elements in the front
       Push(&head,i); 
   } //now a linked list 1->2->3->NULL is formed

struct Node* newlst= CopyList(head); // copies contents into a new linked list

I am compiling the code using Bloodshed Dev C++. I don't get any compilation errors but when I run it, it just crashes. What could be the issue with this? Am I passing the right parameter to the CopyList function?

Your problem lies here, in the else bit:

tail = malloc (sizeof (struct Node));
tail = tail->next;
tail->data = current->data;
tail->next = NULL;

You are allocating a new node and setting tail to point to it (in that first line). Then you are using tail as if it's the old tail. Specifically, that second line will give you a rogue pointer (as you haven't initialised the new node with valid pointers), which will probably crash in the third line when you try to dereference it.

You need something like:

// First, set up the new node.

newList = malloc (sizeof (struct Node));
newList->data = current->data;
newList->next = NULL;

// Then, adjust the tail pointers.

tail->next = newList;
tail = newList;

Actually, looking back at your code, what you probably intended was:

tail->next = malloc (sizeof (struct Node)); // use tail->next, not tail.
tail = tail->next;
tail->data = current->data;
tail->next = NULL;

which achieves the same result.

I suppose I should mention that you really ought to check the return values from malloc in case you run out of memory. You can do this with something like:

tail->next = malloc (sizeof (struct Node)); // use tail->next, not tail.
if (tail->next == NULL) {
    // do something here for recovery.
    return;
}
// Only continue here if the allocation worked.
tail = tail->next;
tail->data = current->data;
tail->next = NULL;

Without checks like that, you will get crashes when you run out of memory.

You are allocating memory for tail, it should be tail->next. Without this you would lose previous pointers. Modified code

struct Node* CopyList(struct Node* head) 
{        
    //.... same as before

    while (current !=NULL)        
    {              
        if(newList==NULL) 
        {              
            //.... same as before
         }              
         else
         {                   
            tail->next = malloc(sizeof(struct Node));                   
            tail= tail->next;                   
            tail->data=current->data;                   
            tail->next = NULL;                   
          }              

          current= current->next;        
     }        

     return(newList); 
}

Shash

If it just dies, that is usually a sing of accessing an invalid pointer. Most likely a null pointer.

Here is your problem:

              tail= malloc(sizeof(struct Node));
              tail= tail->next;

tail points to an unitialised area of memory. So tail->next may be anything.

Try

              tail->next= malloc(sizeof(struct Node));
              tail= tail->next;

Consider this line -

tail = tail->next;

When you are creating the first node in the new list, it's OK, both the newList and tail points to that node.Now think what will happen when a second node will be created in the new list -

tail = malloc(sizeof(struct Node));    // tail points to the new node
tail = tail->next;                     // You are assigning new node's next to tail, but
                                       // did you initialize next to anything?

So next isn't initialized to anything, and you are assigning it to tail, so tail now contains garbage. When you are assigning it some value in the next two lines, your program will certainly crush.

Instead of assigning new node to tail, you need to assign it to tail's next -

tail->next = (struct Node *) malloc(sizeof(struct Node) * 1);

in else block you have written this code

             tail= malloc(sizeof(struct Node));
             tail= tail->next;
             tail->data=current->data;
             tail->next = NULL;

Line 1: tail is pointing a node and all the member of this node is having value as tail has not been initialised.

Line2: tail->next which has garbage value is being assigned to tail. Now tail is not pointing any mallocked memeory. And you lost the pointer of the already mallocked memory

So actually linklist is not being made here