1

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?

2
  • Could you be a bit more specific about what you mean by "just crashes"? Do you mean it segfaults?
    – ajcl
    Aug 5, 2011 at 3:45
  • It says linkedlist.exe stopped works, windows is contacting Microsoft for a solution(I guess that's a crash response of Win 7. I dont see any error message related to the code I'm running). The answer paxdiablo & Shash316 provided fixed the issue.
    – Bharat
    Aug 5, 2011 at 4:16

6 Answers 6

3

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.

1
  • Yes, I had to make tail's next point to the memory allocated by malloc and that fixes the issue. And is there any way I can explicitly print the return values of the malloc or did you just mean I should verify what size of memory I am allocating?
    – Bharat
    Aug 5, 2011 at 4:21
2

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

0

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

0

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

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);
3
  • Firstly, you don't need to cast void pointers, this is done automagically and, if you do it explicitly, it can hide some subtle bugs.
    – paxdiablo
    Aug 5, 2011 at 3:56
  • @paxdiablo: oooo Ok, I didn't know. what kinds of bugs you are talking about? Can you give me some links? Aug 5, 2011 at 3:57
  • If you don't have the correct prototype for malloc (eg, didn't include stdlib.h), it will assume a function returning int, and won't warn you if you explicitly cast it. This will bite you if your ints and pointers are different sizes, for one. Without the cast, the compiler should warn of incompatible types.
    – paxdiablo
    Aug 5, 2011 at 4:00
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.