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

**thames** · 01-08-2013

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;

}

**anduril462** · 01-08-2013

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.

**std10093** · 01-08-2013

Originally Posted by thames

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;

**Barney McGrew** · 01-08-2013

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;
}

**thames** · 01-09-2013

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.

**thames** · 01-09-2013

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

**Barney McGrew** · 01-10-2013

Code:

new_element->prev = element;
if ((new_element->next = element->next))
        element->next->prev = new_element;
element->next = new_element;

edit:

Originally Posted by thames

In fact, I was just trying to understand the codes from Mastering Algorithms With C.

Oh, I didn't catch that.

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

Thread Tools

Search Thread

Display

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

Similar Threads

insert correctly into linked list

Insert into position of Linked List

insert sort linked list???

Insert node in a linked list.

Insert in Linked List ...

Tags for this Thread