C Linked list only contains first element...not sure what happens to rest.

Question

I posted a question a few days ago about a linked list in C. I thought everything was ok then the prof emails us saying that instead of this signature:

int insert_intlist( INTLIST* lst, int n); /* Inserts an int (n) into an intlist from the beginning*/

He accidentally meant:

int insert_intlist( INTLIST** lst, int n); /* Inserts an int (n) into an intlist from the beginning*/

I thought to myself cool now that I have a pointer to a pointer I can move the pointer outside of main and when I return to main I will still have my complete linked list.

He starts off with giving us this:

INTLIST* init_intlist( int n ) 
 {
    INTLIST *lst; //pointer to store node
    lst = (INTLIST *)malloc(sizeof(INTLIST)); //create enough memory for the node
    lst->datum = n; //set the value
    lst->next = NULL; //set the pointer
    return lst; //return the new list
}

Which is simply to initialize the list like so in main:

   if (lst==NULL)
                  lst = init_intlist(i);
               else
                  insert_intlist(lst, i); 

lst is of type INTLIST* so its defined as INTLIST* lst. So I read in some numbers from a text file like 1 3 4 9. It is supposed to create a linked list from this...so the first number would go to init_intlist(1); And that was defined above. Then it grabs the next number 3 in this case and calls insert_intlist(lst, 3). Well here is my insert_intlist and all I want to do is insert at the beginning of the list:

int insert_intlist(INTLIST** lst, int n )
 {
    INTLIST* lstTemp; //pointer to store temporary node to be added to linked list
    lstTemp = (INTLIST *)malloc(sizeof(INTLIST)); //create enough memory for the node
    lstTemp->datum = n; //assign the value

    //check if there is anything in the list,
    //there should be, but just in case
    if(*lst == NULL)
       {
          *lst=lstTemp;
          lstTemp->next=NULL;
       }
    else
       { 
          lstTemp->next = *lst; //attach new node to the front
          *lst = lstTemp; //incoming new node becomes the head of the list
       } 

    return 0; 
 }

So if the list contained 1 initially this function would simply create a new node and then make this temp node->next point to the head of the list (which I thought was lst) and then reassign the head of the list to this new temp node.

It all looks like it is running right but when I try to print my list to the screen it only prints the number 1.

Anyone have any clues as to what I am doing wrong?

Answer 1

The first problem that pops into my mind is that in insert_intlist() you're doing lst = lstTemp;. This should be *lst = lstTemp;. This way you assign to the list pointer that you were supplied rather than to the list pointer pointer (which does not update anything outside of the function).

Answer 2

You're being passed a pointer to a pointer. You want to alter the pointer that is being pointed to, not the pointer to a pointer itself. Does that make sense?

if(lst == NULL)

Here you're checking to see if you were passed a NULL pointer. Good practice for error checking, but not for what you were doing right there. If lst is NULL, then you don't even have a pointer to a pointer, can't do anything, and should return a nonzero error code without doing anything else.

Once you're sure your pointer is not NULL, then you look at the pointer it's pointing to (*lst). The pointed-to pointer is the pointer to the first list item. If that pointer is NULL, then you change it to the new item's pointer. Basically, where you use lst you should be using *lst or (*lst). (REMEMBER: the * operator runs after the -> operator! So to get a field in the object pointed to by the pointer that is pointed to by lst [pant, pant], you use (*lst)->whatever.)

P.S. This kind of pointer work is critical to learn to be a good programmer, especially with C.

P.P.S. The other thing you got wrong is that instead of

insert_intlist(lst, i);

you're supposed to call it like

insert_intlist(&lst, i);

... and, for brownie points, check the return code for errors.

Answer 3

Since you are using a pointer to another pointer in the insert function, you can change at which memory location the latter actually points to. I changed the insert code a bit and it works fine:

int insert_intlist(INTLIST** lst, int n )
{
    INTLIST* lstTemp; //pointer to store temporary node to be added to linked list
    lstTemp = (INTLIST *)malloc(sizeof(INTLIST)); //create enough memory for the node
    lstTemp->datum = n; //assign the value

    //check if there is anything in the list,
    //there should be, but just in case
    if(*lst == NULL)
    {
      lstTemp->next=NULL;
      *lst = lstTemp;
    }
    else
    { 
      lstTemp->next = *lst; //attach new node to the front
      *lst = lstTemp; //incoming new node becomes the head of the list
    } 

return 0; 

}

EDIT: I see you edited your question. In that case, maybe you are calling the insert function in the wrong way in main(). Try this

int main()
{
    INTLIST *head;
    head = init_intlist(42);
    insert_intlist(&head, 41);
    display(head);
    return 0;
}

Answer 4

Check to see if lstTemp->next == NULL after lstTemp->next=lst;

Answer 5

This assignment sucks... Im still not getting the map_list()...

http://stackoverflow.com/questions/2122037/referring-to-c-help-understanding-how-to-write-a-function-within-a-function-l

Did he say we had to use all his functions? it doesn't say his website.