none
Double Linked List and Pointer in C

    Question

  • Hi all,

    I am getting confused by pointer in C. I have dlnode_t and dlist_t as struct to implement double linked list.

    typedef struct dlnode dlnode_t;
    
      struct dlnode
      {
        void *data;   /* A pointer to a generic satellite data payload */
        dlnode_t *next; /* A pointer to the next item in the list */
        dlnode_t *prev; /* A pointer to the previous item in the list */
      };
    
      typedef struct
      {
        dlnode_t *head; /* A pointer to the head node of the list */
        dlnode_t *foot; /* A pointer to the foot node of the list */
        int list_len;  /* Total number of items in the list */
        int size;    /* Size of the list in bytes */
      } dlist_t;
    

     

    int * alloc_data(int val)
    {
      int *rv = safe_malloc(sizeof (int));
      *rv = val;
      return (rv);
    }
    

     

    int main(void)
    {
      dlist_t *list = NULL;
      int *num = NULL, *rv = NULL;
      dlnode_t *tnode = NULL;
    
      list = make_empty_list();
    
      list = insert_in_order(list, alloc_data(5), sizeof (int), cmp_int);
      printf("%d\n",list->list_len);
      printf("%d\n",list->list_len);
      list = insert_in_order(list, alloc_data(2), sizeof (int), cmp_int);
      list = insert_in_order(list, alloc_data(10), sizeof (int), cmp_int);
    
      ...
    }
    

     

    void * safe_malloc(size_t size)
    {
      void * arrays = malloc(size * sizeof (int));
      
      if (arrays == NULL)
      {
        fprintf(stderr, "Memory allocation failed. The program will be terminated.\n");
        exit(EXIT_FAILURE);
      }
    
      return arrays;
    }
    

     

    int cmp_int(const void *a, const void *b)
    {
      int a_int=(int*)a;
      int b_int=(int*)b;
      
      if(a==NULL || b==NULL)
      {
        fprintf(stderr,"Either the value of a or b is NULL.");
        exit(EXIT_FAILURE);
      }
    
      if(a_int>b_int)
        return BIGGER;
      else if(a_int<b_int)
        return SMALLER;
      
      return EQUAL;
    }
    

     

    dlist_t * make_empty_list(void)
    {  
      dlist_t *double_list_pointer = NULL;
      dlist_t double_list;
    
      double_list.foot = NULL;
      double_list.head = NULL;
      double_list.list_len = 0;
      double_list.size = 0;
      double_list_pointer = &double_list;
    
      return double_list_pointer;
    }
    
    dlist_t * insert_in_order(dlist_t *list, void *value, size_t size,
                 int (*cmp_fptr)(const void *, const void *))
    {    
      dlnode_t *current_dlnode = list->head;
      dlnode_t *new_dlnode = safe_malloc(sizeof(dlnode_t));;
      dlnode_t *previous_dlnode=NULL;
      int compare_result = 0;
        
      while (current_dlnode!=NULL)
      {
        compare_result = cmp_fptr(current_dlnode->data, value);
        if(compare_result!=SMALLER)
          continue;
    
        previous_dlnode=current_dlnode;
        current_dlnode=current_dlnode->next;
      }
    
      new_dlnode->data = value;
      new_dlnode->next = current_dlnode;
      new_dlnode->prev = previous_dlnode;
      
      list->list_len=list->list_len+1;
      list->size=list->size+sizeof(new_dlnode);
      
      if(previous_dlnode==NULL)
      {
        current_dlnode=new_dlnode;
        return list;
      }
    
      previous_dlnode->next=new_dlnode;
      if(new_dlnode->next==NULL)
      {
        list->foot=new_dlnode;
      }
      return list;
    }
    


    The first time, after putting an integer into the list, the insert_in_order function will return the list as pointer. list->head still have the same memory address as before. But, the value of list->foot; list->list_len; and list->size are changed. Notice the printf inside the main function, that is where changes occured.

    As a result, the second time, when the list being passed into the insert_in_order function, the value of them changed.

    Example: Suppose the list->list_len should be 1, but it turns out that it gives me a garbage value.

    I don't get it, why all the values, except for head, are changed after the list being returned.

    Sorry, if my english is bad.

    Monday, August 01, 2011 3:29 AM

Answers

  • Based on your code, your list is an ASC sorted list. There is no need to return *list since after the insert_in_order function call, the *list has the new node already. The function might be

    BOOL insert_in_order(dlist_t *list, void *value, size_t size,

                 int (*cmp_fptr)(const void *, const void *))

     

    What does a garbage value mean?

     

    The header should not be changed if insert value is not smaller than any node data in your list. The header stores the first node of the dlnode_t. 


    Senior Support Engineer
    • Marked as answer by Rob Pan Friday, August 05, 2011 8:13 AM
    Monday, August 01, 2011 7:51 AM

All replies

  • Hi,

    I didn't ready your codes carefully, but obviously you can not return a pointer to the variable on stack in make_empty_list.

    RenJie

    Monday, August 01, 2011 4:44 AM
  • Based on your code, your list is an ASC sorted list. There is no need to return *list since after the insert_in_order function call, the *list has the new node already. The function might be

    BOOL insert_in_order(dlist_t *list, void *value, size_t size,

                 int (*cmp_fptr)(const void *, const void *))

     

    What does a garbage value mean?

     

    The header should not be changed if insert value is not smaller than any node data in your list. The header stores the first node of the dlnode_t. 


    Senior Support Engineer
    • Marked as answer by Rob Pan Friday, August 05, 2011 8:13 AM
    Monday, August 01, 2011 7:51 AM
  • There are numerous problems with your code.  The following are just the obvious ones at first glance:

         There is no declaration (prototype or definition) in scope when alloc_data calls safe_malloc.  The compiler must assume safe_malloc returns int which is obviously false and should lead to a required diagnostic.

         The same problem exists when main calls make_empty_list.

         make_empty_list returns the address of an automatic object.  The object will cease to exist as soon as make_empty_list returns.  It is illegal for main to attempt to use that object or make any use of the returned value.

         The same missing prototype problem exists when main calls insert_in_order.  Furthermore, cmp_int is undefined at this point.  The compiler has no idea what value to pass but must assume the value is an int.  This should result in a required diagnostic at the point where insert_in_order is defined.

         On each call to insert_in_order, previous_dlnode is set to NULL.  On the first call,          list->head is also NULL (courtesy of make_empty_list) and that value is assigned to current_dlnode.  The while loop is skipped, values are stored in *new_dlnode, list->list_len and list->size are updated, and list->head is NOT updated.  previous_dlnode is still NULL so you return WITHOUT EVER UPDATING list->head.  On the second call, this process is repeated.  list->head is NEVER updated!

         You could save a lot of typing (and the possibility of typing errors) if you replace lines like list->list_len=list->list_len+1; with list->list_len += 1; (and in this case the more idiomatic  list->list_len++;).

         Why in main do you print list->len twice in succession?

    Saturday, August 06, 2011 11:05 PM