Incrementing int in linked-list

[latte123]

Hi all -
I'm trying to write a linked-list that automatically increments its integer member as each node is added, but I haven't quite got things right as yet.

This is the code I've done so far -

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>  


struct node { 
    int index;    
    struct node *next;   
} ;


/* Create a new list */ 
struct node *list_new(int i)
{ 
  struct node *mylist = NULL; 
  mylist = malloc(sizeof(struct node));   
  mylist->index = i;  
  mylist->next = NULL;   
  return mylist; 
} 



/* Function to add data to end of a list  */ 
void list_append(struct node *mylist)
{  
   
   int i; 
   
   /* A pointer to iterate along the list */ 
   struct node *ptr = NULL; 
   
   /* Now, create a new node using the data. */ 
   struct node *newnode = NULL; 
   newnode = malloc(sizeof(struct node));  
       
  
  /* Is our existing list null? */ 
  /* If so, our "list" is just the newly-created node. */ 
   if(mylist == NULL) 
     {  
        mylist = newnode;         
     }             
           
   else 
     {  
        
         for( ptr = mylist; ptr->next != NULL; ptr = ptr->next ) 
           { 
             /* Iterate through the list until we find the last node */   
             // i = ptr->index;
             i = ptr->index; 
           }         
      
       /* Add the new node to the end of the list. */ 
       /* In other words: the last ptr->next WAS null, but it is */ 
       /* now pointing to newnode. */  
       ptr->next = newnode; 
       newnode->index = i+1; 
       newnode->next = NULL;  
    
     }     
       
}  /* End of list_append  */  

    
    
/* Free the list memory. */ 
void free_list(struct node *mylist) 
{ 
  /* We create TWO pointers. */ 
  /* ptr is used to iterate through the list. */ 
  /* tmp (which points to the same place) is used to */ 
  /* actually free the memory. */    
   struct node *ptr, *tmp = NULL;        
          
  /* Check that the list is non-null. */   
   if(mylist != NULL) 
     {  
                          
         for( ptr = mylist; ptr->next != NULL; ptr = ptr->next ) 
           { 
             /* Iterate through the list */   
              printf( "Freeing %d\n",  ptr->index );  
              tmp = ptr;              
              free(tmp);                   
           }         
      
       /* Free the last element of the list */ 
       /* (where ptr->next IS null). */        
        printf( "Freeing %d\n",  ptr->index ); 
        free(ptr);   
    
     }     
    
}     
               

void print_list(struct node *mylist)
{ 
   /* A pointer for iterating. */ 
   struct node *ptr    = NULL;  
    
   /* Iterate along the list.  */ 
    for( ptr = mylist; ptr->next != NULL; ptr = ptr->next )     
       { 
          printf( "mylist->index = %d\n",  ptr->index );                    
       }         
    
    /* For the last node (where ->next IS NULL), we need to print */ 
    /* it outside the loop. */ 
    printf( "mylist->index = %d\n",  ptr->index ); 
    
}


int main() 
{ 

struct node *my_list = list_new(0); 

list_append(my_list);  
list_append(my_list);  
list_append(my_list);  
list_append(my_list);  
list_append(my_list);  
list_append(my_list);  

print_list(my_list); 

free_list(my_list);  

return 0;  
 
}

This compiles fine, but when I run it, I get this -
mylist->index = 0
mylist->index = 134520821
mylist->index = 1
mylist->index = 134520822
mylist->index = 2
mylist->index = 134520823
mylist->index = 3
Freeing 0
Freeing 134520821
Freeing 1
Freeing 134520822
Freeing 2
Freeing 134520823
Freeing 3
andy@obsidian ~/testdir $

So - what am I doing wrong? It seems to be printing the *address* of the int at each alternate step - not the int itself.

Many thanks in advance for your help!
Bye for now -
- Andy

[dwks]

  /* Is our existing list null? */
  /* If so, our "list" is just the newly-created node. */
   if(mylist == NULL)
     { 
        mylist = newnode;        
     }

This assignment doesn't actually have any lasting effect. All you're doing is changing the local parameter "mylist" within list_append to point to something else; but the function which called list_append() won't see the changes. For that, you'd need a struct node**, or you could return the modified struct node*. Of course this issue doesn't actually arise in this case because main() calls list_new(0) and list_append() never sees an empty list.

As for the strange numbers... well, you don't initialize i inside list_append(). If the for loop on line 49 runs at least once then i will be set to something; but otherwise, if there is exactly one element in the list you'll get an uninitialized i (the loop body will never run). Thus the second element in the list gets the number 134520821 in your case. Thereafter the numbering works as follows: each element will be assigned an index one greater than the previous previous element. Just because of the way your loop is set up: at the end of the loop you might go ptr=ptr->next, break since ptr->next is NULL, i is still referring to the old ptr's index.

[edit] In other words, the first index is given; the second is random; the third is the first+1; the fourth is the second+1; the fifth is the third+1; and so on. [/edit]

I think that explains all the behaviour you're seeing. By the way, an easy way to fix list_append's loop is something like

         for( ptr = mylist; ptr->next != NULL; ptr = ptr->next ) {}  // traverse
       
       ptr->next = newnode; 
       newnode->index = ptr->index + 1;  // index is one higher
       newnode->next = NULL;

Unless you're trying to find the maximum index or something, but then you'd look for a max index as you traversed the list.

Similar issue with free_list()... your code there is correct I think, but you've kind of pulled out a special case for the last element. Why not just do it all in a simple loop? By the way, free(NULL) is perfectly safe.

while(ptr != NULL) {
    struct node *next = ptr->next;
    free(ptr);
    ptr = next;
}

Okay, that's about it... one last note, print_list() will crash if given a NULL list. Also, you may want to be more consistent with your indentation. It will make your code easier to understand.

[edit] Also! malloc.h is ancient and you shouldn't use it. These days malloc() and free() and realloc() are in stdlib.h. [/edit]

[iMalc]

So you want a count of the number of items to be held within the list?
In that case you want two different structs. One is the node which has data plus a pointer to the next node, and one is the list itself which has the count and a pointer to the first node.

Oh, actually I realise that you've called it 'index', which implies that you want to look up an item by its index. That means you're using the wrong data structure for the job. A list is goot at inserting and removing nodes in the middle, which would totally screw up your indexes, and a list is bad at finding an item by index.
You should be using some kind of resizeable array.

[latte123]

Hi dwks - thanks for that! Very helpful!
This will be a big help with my getting a good solid understanding of linked-lists.
Thanks again, bye for now -
- Andy

[latte123]

Hi iMalc - thanks for your reply -
I just called the member "index" as a simple name - I'm not really wanting to look up an item by index.
The only thing I wanted to try here was to get the incrementing behaviour working.
I'm sure I'll be ok looking up an item by looking for its value...

Thanks again - bye for now -
- Andy

[nonpuz]

Deleted my own post: didn't read the ones above thoroughly enough and double-posted information

[latte123]

Hi nonpuz, thanks for that - that's helpful too!

Looks like I was more-or-less 80-percent-ish "on the right track". Just a few little bits got past me.....

Thanks everyone - I'm very happy with all of your help - much appreciated!
I'll mark this as solved now.
- Andy

[latte123]

Problem solved - thanks to all who have replied.
- Andy