CODEWITHSUNDEEP
cdata-structureslinked-list
Bharat
Bharat

Reputation: 3010

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;
             }
             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?

Upvotes: 1

Views: 327

Answers (6)

sukumar
sukumar

Reputation: 129

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

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 882716

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.

Upvotes: 3

MD Sayem Ahmed
MD Sayem Ahmed

Reputation: 29186

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);

Upvotes: 0

Nikki Locke
Nikki Locke

Reputation: 2951

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;

Upvotes: 0

Kratz
Kratz

Reputation: 4340

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

Upvotes: 0

Shash316
Shash316

Reputation: 2218

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

Upvotes: 2

Related Questions