Thread: What's happening in that Circular List clist_rem_next function?

  1. #1
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193

    Question What's happening in that Circular List clist_rem_next function?

    Good afternoon everyone. I already studied some illustrations from the book for the Circular lists. Therefore, my problem is that I don't know what's the purpose of writing

    Code:
    old_element = element->next;
    inside clist_rem_next (a function to remove the node after the specified one).

    Code:
     
    #ifndef CLIST_H
    #define CLIST_H
    
    #include <stdlib.h>
    
    typedef struct CListElmt_{
        
     void* data; 
     struct CListElmt_* next;
         
    } CListElmt;
    
    typedef struct CList_ {
        
     int   size;
     int   (*match)(const void *key1, const void* key2);
     void  (*destroy)(void* data);
     
     CListElmt *head;
    
    } CList;         
    
    /* public interface */ 
    
    void clist_init(CList* list, void (*destroy)(void* data));
    void clist_destroy(CList* list);
    int clist_ins_next(CList* list, CListElmt* element, const void* data);
    int clist_rem_next(CList* list, CListElmt* element, void** data);
    
    #define clist_size(list) ((list)->size)
    #define clist_head(list) ((list)->head)
    #define clist_data(element) ((element)->data)
    #define clist_next(element) ((element)->next)
    
    #endif
    Code:
     
    #include <stdlib.h> 
    #include <string.h>
    #include "Headers/clist.h"
    
    void clist_init(CList* list, void (*destroy)(void* data))
    {
       /* initialize the list */ 
       list->size = 0; 
       list->destroy = destroy; 
       list->head = NULL;    
       
       return;
    }     
    
    void clist_destroy(CList* list)
    { 
       void* data; 
       
       /* remove each element */ 
       while(clist_size(list) > 0) 
       {
          if(clist_rem_next(list, list->head, (void**)&data) == 0 
             && list->destroy != NULL) 
          {
            /* call a user-defined function to free dinamically allocated data */
            list->destroy(data);      
          }                 
       }
       /* no operations are allowed now, but clear the structure as a precaution */
       memset(list, 0, sizeof(CList));              
       return;
    }     
    
    int clist_ins_next(CList* list, CListElmt* element, const void* data) 
    { 
       CListElmt* new_element;
       /* allocate storage for the element */ 
       if((new_element = (CListElmt*)malloc(sizeof(CListElmt))) == NULL)
          return -1;
       /* insert the element into the list */ 
       new_element->data = (void*) data; 
       if(clist_size(list) == 0)
       { 
          /* handle insertion when the list is empty */
          new_element->next = new_element;
          list->head = new_element;
       }
       else 
       { 
          /* handle insertion when the list is not empty */ 
          new_element->next = element->next; 
          element->next = new_element;   
       }
       /* adjust the size of the list to account for the inserted element */ 
       list->size++;
       return 0;
    }
    
    int clist_rem_next(CList* list, CListElmt* element, void** data)
    { 
       CListElmt* old_element;
       /* don't allow removal from an empty list */ 
       if(clist_size(list) == 0) 
         return -1; 
       /* remove the element from the list */ 
       *data = element->next->data; 
       if(element->next == element) 
       { 
         /* handle removing the last element */ 
         old_element = element->next; 
         list->head = NULL;
       }
       else 
       { 
         /* handle removing other than the last element. */ 
         old_element = element->next; 
         element->next = element->next->next;
         if(old_element == clist_head(list))
           list->head = old_element->next;    
       }
       free(old_element);
       list->size--;
       return 0;        
    }
    Code:
     
    /*****************************************************************************
    *                                                                            *
    *  ex-1.c                                                                    *
    *  ======                                                                    *
    *                                                                            *
    *  Description: Illustrates using a circular list (see Chapter 5).           *
    *                                                                            *
    *****************************************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #include "Headers/clist.h"
    
    /*****************************************************************************
    *                                                                            *
    *  ------------------------------ print_list ------------------------------  *
    *                                                                            *
    *****************************************************************************/
    
    static void print_list(const CList *list) {
    
    CListElmt          *element;
    
    int                *data,
                       size,
                       i;
    
    /*****************************************************************************
    *                                                                            *
    *  Display the circular list.                                                *
    *                                                                            *
    *****************************************************************************/
    
    fprintf(stdout, "List size is %d (circling twice)\n", clist_size(list));
    
    size = clist_size(list);
    element = clist_head(list);
    
    /*****************************************************************************
    *                                                                            *
    *  Iterate twice through the circular list to verify the circular links.     *
    *                                                                            *
    *****************************************************************************/
    
    i = 0;
    
    while (i < size * 2) {
    
       data = clist_data(element);
       fprintf(stdout, "list[%03d]=%03d\n", (i % size), *data);
       element = clist_next(element);
       i++;
    
    }
    
    return;
    
    }
    
    /*****************************************************************************
    *                                                                            *
    *  --------------------------------- main ---------------------------------  *
    *                                                                            *
    *****************************************************************************/
    
    int main(int argc, char **argv) {
    
    CList              list;
    CListElmt          *element;
    
    int                *data,
                       i;
    
    /*****************************************************************************
    *                                                                            *
    *  Initialize the circular list.                                             *
    *                                                                            *
    *****************************************************************************/
    
    clist_init(&list, free);
    
    /*****************************************************************************
    *                                                                            *
    *  Perform some circular list operations.                                    *
    *                                                                            *
    *****************************************************************************/
    
    element = clist_head(&list);
    
    for (i = 0; i < 10; i++) {
    
       if ((data = (int *)malloc(sizeof(int))) == NULL)
          return 1;
    
       *data = i + 1;
    
       if (clist_ins_next(&list, element, data) != 0)
          return 1;
    
       if (element == NULL)
          element = clist_next(clist_head(&list));
       else
          element = clist_next(element);
    
    }
    
    print_list(&list);
    
    element = clist_head(&list);
    
    for (i = 0; i < 10; i++)
       element = clist_next(element);
    
    data = clist_data(element);
    fprintf(stdout, "Circling and removing an element after the one containing "
       "%03d\n",*data);
    
    if (clist_rem_next(&list, element, (void **)&data) != 0)
       return 1;
    
    free(data);
    print_list(&list);
    
    element = clist_head(&list);
    
    for (i = 0; i < 15; i++)
       element = clist_next(element);
    
    data = clist_data(element);
    fprintf(stdout, "Circling and inserting 011 after the element containing "
       "%03d\n", *data);
    
    if ((data = (int *)malloc(sizeof(int))) == NULL)
       return 1;
    
    *data = 11;
    if (clist_ins_next(&list, element, data) != 0)
       return 1;
    
    print_list(&list);
    
    /*****************************************************************************
    *                                                                            *
    *  Destroy the circular list.                                                *
    *                                                                            *
    *****************************************************************************/
    
    fprintf(stdout, "Destroying the list\n");
    clist_destroy(&list);
    
    return 0;
    
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Code:
    /* remove the element from the list */
    *data = element->next->data; 
    if(element->next == element) 
    { 
      /* handle removing the last element */
      old_element = element->next; 
      list->head = NULL;
    }
    else
    { 
      /* handle removing other than the last element. */
      old_element = element->next; 
      element->next = element->next->next;
      if(old_element == clist_head(list))
        list->head = old_element->next;    
    }
    free(old_element);
    Broadly speaking, there are two steps to deleting a node in any type of linked list (single, double, circular). First, you must update the list to exclude that node, adjusting the next/prev pointers of it's neighbors. Second, you must free the memory associated with that node.

    The clist_rem_next function removes the node after the "current" node, i.e. after whatever node element points to. Thus, old_element is set to point to that node, element->next, so we can save it for deleting/freeing later. If we don't do that, then what do we pass to the free function (line 81)? element->next no longer points to the node we wish to delete. We would have lost that memory, creating a memory leak.

  3. #3
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    Quote Originally Posted by anduril462 View Post
    so we can save it for deleting/freeing later. If we don't do that, then what do we pass to the free function (line 81)? element->next no longer points to the node we wish to delete. We would have lost that memory, creating a memory leak.
    I see! many thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 01-10-2013, 04:09 AM
  2. Help on circular list!
    By flexo87 in forum C Programming
    Replies: 2
    Last Post: 01-30-2009, 02:35 PM
  3. Circular array list
    By stimpyzu in forum C++ Programming
    Replies: 3
    Last Post: 03-07-2004, 02:28 PM
  4. Circular Linked List ??
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-14-2001, 02:12 PM
  5. Is it circular link list?
    By BigAl in forum C Programming
    Replies: 5
    Last Post: 11-01-2001, 06:48 PM

Tags for this Thread