Like Tree3Likes
  • 1 Post By anduril462
  • 1 Post By std10093
  • 1 Post By Barney McGrew

What's happening in that Double Linked List insert next?

This is a discussion on What's happening in that Double Linked List insert next? within the C Programming forums, part of the General Programming Boards category; Good evening. Can you explain to me the code below from function dlist_ins_next? Elysia, I turned back and I saw ...

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

    What's happening in that Double Linked List insert next?

    Good evening. Can you explain to me the code below from function dlist_ins_next? Elysia, I turned back and I saw I need to read that book you recommended me if I want to read other books. But not now . Back to the code:

    I couldn't understand this (last else of dlist_ins_next function):

    Code:
    if(element->next == NULL)
            list->tail = new_element;
          else 
             element->next->prev = new_element;  
          element->next = new_element;
    the srcs:

    Code:
    #ifndef DLIST_H
    #define DLIST_H
    
    #include <stdlib.h>
    
    typedef struct DListElmt_{
        
      void* data; 
      struct DListElmt_ *prev; 
      struct DListElmt_ *next;    
    
    } DListElmt;    
    
    typedef struct DList_ {
        
      int size; 
      int  (*match)(const void *key1, const void* key2);
      void (*destroy)(void* data);
      DListElmt* head; 
      DListElmt* tail;    
    
    } DList;
    
    /* public interface */
    
    void dlist_init(DList *list, void (*destroy)(void *data));
    void dlist_destroy(DList *list);
    int dlist_ins_next(DList *list, DListElmt *element, const void *data);
    int dlist_ins_prev(DList *list, DListElmt *element, const void *data);
    int dlist_remove(DList *list, DListElmt *element, void **data);
    
    #define dlist_size(list) ((list)->size)
    #define dlist_head(list) ((list)->head)
    #define dlist_tail(list) ((list)->tail)
    #define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
    #define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
    #define dlist_data(element) ((element)->data)
    #define dlist_next(element) ((element)->next)
    #define dlist_prev(element) ((element)->prev)    
    
    
    #endif
    Code:
    #include "Headers/dlist.h"
    #include <stdlib.h>
    #include <string.h> 
    
    void dlist_init(DList* list, void (*destroy)(void* data) )
    {
        list->size = 0;
        list->destroy = destroy;
        list->head = NULL; 
        list->tail = NULL;
    
        return;
    }
    
    void dlist_destroy(DList* list) 
    {
       void* data; 
       
       /* remove each element */ 
       while(dlist_size(list) > 0)
       {
           if(dlist_remove(list, dlist_tail(list), (void**)&data) == 0    &&
           list->destroy != NULL) 
           { 
             /* call a user-defined function to free dynamically allocated data */
             list->destroy(data);  
           }        
        }     
        memset(list, 0, sizeof(DList));
        return;
    }    
    
    // insert node after the specified one. 
    int dlist_ins_next(DList* list, DListElmt* element, const void* data) 
    { 
       DListElmt* new_element;
       
       /* don't allow a NULL element unless the list is empty */
       if(element == NULL && dlist_size(list) != 0)
         return -1;    
       /* allocate storage for the element */
       if((new_element = (DListElmt*)malloc(sizeof(DListElmt))) == NULL)
         return -1;
       /* insert the new element into the list */
       new_element->data = (void*) data;
       
       if(dlist_size(list) == 0)  
       {
          list->head = new_element;
          list->head->prev = NULL;
          list->head->next = NULL;
          list->tail = new_element;   
       }       
       else {
          
          /* handle insertion when the list is not empty */
          new_element->next = element->next;
          new_element->prev = element;
          
          if(element->next == NULL)
            list->tail = new_element;
          else 
             element->next->prev = new_element;  
          element->next = new_element;        
       }
       list->size++;
       return 0;
    }     
    
    int dlist_ins_prev(DList* list, DListElmt* element, const void* data) 
    { 
       DListElmt*  new_element;
       /* don't allow a NULL element unless the list is empty */ 
       if(element == NULL && dlist_size(list) != 0)
         return -1;
       /* allocate storage to be managed by the abstract datatype  */ 
       if((new_element = (DListElmt*)malloc(sizeof(DListElmt))) == NULL)
         return -1;
       /* insert the new element into the list */
       new_element->data = (void*) data;
       if(dlist_size(list) == 0)
       {
          /* handle insertion when the list is empty */
          list->head = new_element;
          list->head->prev = NULL; 
          list->head->next = NULL; 
          list->tail = new_element;   
       }         
       else 
       { 
          /* handle insertion when the list is not empty */ 
          new_element->next = element;
          new_element->prev = element->prev;       
           if(element->prev == NULL) 
             list->head = new_element;
           else
             element->prev->next = new_element;
           element->prev = new_element;     
       }        
       list->size++;
       return 0;
     }     
     
     int dlist_remove(DList* list, DListElmt* element, void** data) 
     { 
        /* don't allow a NULL element or removal from an empty list */
        if(element == NULL || dlist_size(list) == 0)
          return -1;
        /* remove the element from the list */
        *data = element->data;
        if(element == list->head) 
        {
           /* handle removal from the head of the list */
           list->head = element->next; 
           if(list->head == NULL)
              list->tail = NULL;    
           else 
              element->next->prev = NULL;   
        }           
        else 
        {
          /* handle removal from other than the head of the list */
          element->prev->next = element->next;
          if(element->next == NULL)
            list->tail = element->prev; 
          else 
            element->next->prev = element->prev;        
        } 
        /* free the storage allocated by the abstract datatype */ 
        free(element);
        /* adjust the size of the list to account for the removed element */
        list->size--;
        return 0;  
     }
    Code:
    #include "Headers/dlist.h"
    #include <stdio.h> 
    #include <stdlib.h> 
    
    /*****************************************************************************
    *                                                                            *
    *  ------------------------------ print_list ------------------------------  *
    *                                                                            *
    *****************************************************************************/
    
    void print_list(const DList *list) {
    
    DListElmt          *element;
    
    int                *data,
                       i;
    
    /*****************************************************************************
    *                                                                            *
    *  Display the doubly-linked list.                                           *
    *                                                                            *
    *****************************************************************************/
    
    fprintf(stdout, "List size is %d\n", dlist_size(list));
    
    i = 0;
    element = dlist_head(list);
    
    while (1) {
    
       data = dlist_data(element);
       fprintf(stdout, "list[%03d]=%03d\n", i, *data);
    
       i++;
    
       if (dlist_is_tail(element))
          break;
       else
          element = dlist_next(element);
    
    }
    
    return;
    
    }
    
    /*****************************************************************************
    *                                                                            *
    *  --------------------------------- main ---------------------------------  *
    *                                                                            *
    *****************************************************************************/
    
    int main(int argc, char **argv) {
    
    DList              list;
    DListElmt          *element;
    
    int                *data,
                       i;
    
    /*****************************************************************************
    *                                                                            *
    *  Initialize the doubly-linked list.                                        *
    *                                                                            *
    *****************************************************************************/
    
    dlist_init(&list, free);
    
    /*****************************************************************************
    *                                                                            *
    *  Perform some doubly-linked list operations.                               *
    *                                                                            *
    *****************************************************************************/
    
    element = dlist_head(&list);
    
    for (i = 10; i > 0; i--) {
    
       if ((data = (int *)malloc(sizeof(int))) == NULL)
          return 1;
    
       *data = i;
    
       if (dlist_ins_prev(&list, dlist_head(&list), data) != 0)
          return 1;
    
    }
    
    print_list(&list);
    
    element = dlist_head(&list);
    
    for (i = 0; i < 8; i++)
       element = dlist_next(element);
    
    data = dlist_data(element);
    fprintf(stdout, "Removing an element after the one containing %03d\n", *data);
    
    if (dlist_remove(&list, element, (void **)&data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Inserting 011 at the tail of the list\n");
    
    *data = 11;
    if (dlist_ins_next(&list, dlist_tail(&list), data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Removing an element at the tail of the list\n");
    
    element = dlist_tail(&list);
    if (dlist_remove(&list, element, (void **)&data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Inserting 012 just before the tail of the list\n");
    
    *data = 12;
    if (dlist_ins_prev(&list, dlist_tail(&list), data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Iterating and removing the fourth element\n");
    
    element = dlist_head(&list);
    element = dlist_next(element);
    element = dlist_prev(element);
    element = dlist_next(element);
    element = dlist_prev(element);
    element = dlist_next(element);
    element = dlist_next(element);
    element = dlist_next(element);
    
    if (dlist_remove(&list, element, (void **)&data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Inserting 013 before the first element\n");
    
    *data = 13;
    if (dlist_ins_prev(&list, dlist_head(&list), data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Removing an element at the head of the list\n");
    
    if (dlist_remove(&list, dlist_head(&list), (void **)&data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Inserting 014 just after the head of the list\n");
    *data = 14;
    
    if (dlist_ins_next(&list, dlist_head(&list), data) != 0)
       return 1;
    
    print_list(&list);
    
    fprintf(stdout, "Inserting 015 two elements after the head of the list\n");
    
    if ((data = (int *)malloc(sizeof(int))) == NULL)
       return 1;
    
    *data = 15;
    element = dlist_head(&list);
    element = dlist_next(element);
    
    if (dlist_ins_next(&list, element, data) != 0)
       return 1;
    
    print_list(&list);
    
    i = dlist_is_head(dlist_head(&list));
    fprintf(stdout, "Testing dlist_is_head...Value=%d (1=OK)\n", i);
    i = dlist_is_head(dlist_tail(&list));
    fprintf(stdout, "Testing dlist_is_head...Value=%d (0=OK)\n", i);
    i = dlist_is_tail(dlist_tail(&list));
    fprintf(stdout, "Testing dlist_is_tail...Value=%d (1=OK)\n", i);
    i = dlist_is_tail(dlist_head(&list));
    fprintf(stdout, "Testing dlist_is_tail...Value=%d (0=OK)\n", i);
    
    /*****************************************************************************
    *                                                                            *
    *  Destroy the doubly-linked list.                                           *
    *                                                                            *
    *****************************************************************************/
    
    fprintf(stdout, "Destroying the list\n");
    dlist_destroy(&list);
    
    return 0;
    
    }
    Last edited by thames; 01-08-2013 at 04:13 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,495
    EDIT: I grabbed the code from the remove function by mistake, here's the updated reply.

    In a linked list, it is common to use NULL to terminate the list. Thus,
    Code:
    if(element->next == NULL)  // if the next node is NULL, i.e. 'element' is the last node of the list
        list->tail = new_element;  // then make tail point to the new 'element'
    else  // inserting a node into the middle of the list, after 'element'
        element->next->prev = new_element;  // update the next node's prev pointer to point to the new node
    element->next = new_element;  // update element's next pointer to point to the new node
    I strongly suggest you draw out some sample linked lists on paper, with the next and prev arrows between the nodes, and label head and tail. Practice on paper inserting and deleting nodes from the beginning (head), middle and end (tail) of the list. Pay careful attention to how the arrows have to be readjusted to keep the list in working order.
    Last edited by anduril462; 01-08-2013 at 04:39 PM. Reason: changed "removing" to "inserting"
    thames likes this.

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by thames View Post
    Code:
    if(element->next == NULL)
            list->tail = new_element;
          else 
             element->next->prev = new_element;  
          element->next = new_element;
    At first I guess you understand that this code is equivalent to this
    (I just add the brackets)
    Code:
    if(element->next == NULL)
    {
            list->tail = new_element;
    }  
    else
    {
             element->next->prev = new_element;  
    }
    element->next = new_element;
    This code says :
    Code:
    if(element->next == NULL)
    /* If what is pointed by next pointer of element is NULL */
    {
            
            /* Then put the tail pointer of the list to point to the
                 new_element */
            list->tail = new_element;
    }  
    else
    {
              /* If not, then make what is pointed by the previous pointer
                  of
                  (what is pointed by the next pointer of element), to point
                  to the new_element */
              /* In other words of code you say :
             (element->next)->prev = new_element;  
             */
             element->next->prev = new_element;  
    }
    /* Just place the next pointer of the element pointing to the new_element */
    element->next = new_element;
    thames likes this.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    You haven't really designed this library in a very flexible manner. Code that deals with memory allocation and the data contained within each list element is better handled by the code using the library, rather than the library itself. Furthermore, it's hardly useful to hide the underlying type of DList from the person using the library unless there's a good reason, such as the case where the type is likely to change from implementation to implementation (FILE is a good example of this.) Consider the simplicity of the following implementation of a singly linked list library:

    list.h:
    Code:
    struct elem {
        void *value;
        struct elem *next;
    };
    
    extern struct elem *list_delete(struct elem *ptr, struct elem *list);
    
    extern struct elem *list_cons(struct elem *ptr, struct elem *list);
    
    extern struct elem *list_ref(const struct elem *list, unsigned int n);
    list.c:
    Code:
    #include "list.h"
    
    struct elem *list_delete(struct elem *ptr, struct elem *list)
    {
        struct elem *lp;
    
        if (list == ptr)
            return ptr->next;
        for (lp = list; lp; lp = lp->next)
            if (lp->next == ptr) {
                lp->next = ptr->next;
                break;
            }
        return list;
    }
    
    struct elem *list_cons(struct elem *ptr, struct elem *list)
    {
        ptr->next = list;
        return ptr;
    }
    
    struct elem *list_ref(const struct elem *list, unsigned int n)
    {
        while (n-- && list)
            list = list->next;
        return (struct elem *) list;
    }
    And a sample translation unit, similar to the one you've provided, demonstrating the use of the library:
    main.c:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "list.h"
    
    static struct elem *new(int value)
    {
        struct elem *r;
    
        if (!(r = malloc(sizeof *r)) || !(r->value = malloc(sizeof value)))
            exit(EXIT_FAILURE);
        *(int *) r->value = value;
        return r;
    }
    
    static void delete(struct elem *ptr)
    {
        free(ptr->value);
        free(ptr);
    }
    
    int main(void)
    {
        struct elem *list = 0, *ptr;
        int i;
    
        for (i = 10; i > 0; i--)
            list = list_cons(new(i), list);
    
        list = list_delete((ptr = list_ref(list, 8)), list);
        delete(ptr);
    
        for (ptr = list; ptr; ptr = ptr->next)
            printf("%d\n", *(int *) ptr->value);
        return 0;
    }
    nonpuz likes this.

  5. #5
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    You haven't really designed this library in a very flexible manner.
    In fact, I was just trying to understand the codes from Mastering Algorithms With C.

  6. #6
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    I think I got it while I was looking at some illustrations.


    Code:
    element->next->prev = new_element;
    element->next = new_element;
    the referenced element is the node after the current node so, new_element is going to be put between the current element and its successor and then I set prev from the third node (element->next) to point to the new element with prev. After that, I make the current element point to new_element with next. i.e:

    element -----> new_element ----> element->next
    element.next ------> new_element <--------- element.prev

  7. #7
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    Code:
    new_element->prev = element;
    if ((new_element->next = element->next))
            element->next->prev = new_element;
    element->next = new_element;
    edit:
    Quote Originally Posted by thames View Post
    In fact, I was just trying to understand the codes from Mastering Algorithms With C.
    Oh, I didn't catch that.
    Last edited by Barney McGrew; 01-10-2013 at 03:13 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. insert correctly into linked list
    By coolprogrammer in forum C Programming
    Replies: 3
    Last Post: 09-28-2009, 02:54 PM
  2. Insert into position of Linked List
    By Suchy in forum C++ Programming
    Replies: 2
    Last Post: 02-18-2008, 09:02 AM
  3. insert sort linked list???
    By vanella*Flavor in forum C++ Programming
    Replies: 4
    Last Post: 10-25-2005, 07:42 PM
  4. Insert node in a linked list.
    By antonis in forum C Programming
    Replies: 2
    Last Post: 10-22-2005, 02:30 PM
  5. Insert in Linked List ...
    By yescha in forum C Programming
    Replies: 4
    Last Post: 11-28-2001, 03:23 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21