C Program To Maintain a Double Linked List

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

/* structure representing a node of the doubly linked list */
struct dnode
{
      struct dnode *prev ;
      int data ;
      struct dnode * next ;
} ;
typedef struct dnode dnode;
void d_append ( dnode **, int ) ;
void d_addatbeg ( dnode **, int ) ;
void d_addafter ( dnode *, int , int ) ;
void d_display ( dnode * ) ;
int d_count ( dnode *  ) ;
void d_delete ( dnode **, int ) ;

void main( )
{
      dnode *p ;

      p = NULL ;  /* empty doubly linked list */
      d_append ( &p , 11 ) ;
      d_append ( &p , 2 ) ;
      d_append ( &p , 14 ) ;
      d_append ( &p , 17 ) ;
      d_append ( &p , 99 ) ;
     
      d_display ( p ) ;
      printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

      d_addatbeg ( &p, 33 ) ;
      d_addatbeg ( &p, 55 ) ;

      d_display ( p ) ;
      printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

      d_addafter ( p, 4, 66 ) ;
      d_addafter ( p, 2, 96 ) ;

      d_display ( p ) ;
      printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

      d_delete ( &p, 55 ) ;
      d_delete ( &p, 2 ) ;
      d_delete ( &p, 99 ) ;

      d_display ( p ) ;
      printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
}

/* adds a new node at the end of the doubly linked list */
void d_append ( dnode **s, int num )
{
      dnode *r, *q = *s ;

      /* if the linked list is empty */
      if ( *s == NULL )
      {
            /*create a new node */
            *s = malloc ( sizeof ( dnode ) ) ;
            ( *s ) -> prev = NULL ;
            ( *s ) -> data = num ;
            ( *s ) -> next = NULL ;
      }
      else
      {
            /* traverse the linked list till the last node is reached */
            while ( q -> next != NULL )
                  q = q -> next ;
            /* add a new node at the end */
            r = malloc ( sizeof ( dnode ) ) ;
            r -> data = num ;
            r -> next = NULL ;
            r -> prev = q ;
            q -> next = r ;
      }
}

/* adds a new node at the begining of the linked list */
void d_addatbeg ( dnode **s, int num )
{
      dnode *q ;
      /* create a new node */
      q = malloc ( sizeof ( dnode ) ) ;
      /* assign data and pointer to the new node */
      q -> prev = NULL ;
      q -> data = num ;
      q -> next = *s ;

      /* make new node the head node */
      if((*s)!= NULL)
{
        ( *s ) -> prev = q ;
      }
*s = q ;
}

/* adds a new node after the specified number of nodes */
void d_addafter ( dnode *q, int loc, int num )
{
      dnode *temp ;
      int i ;
      /* skip to desired portion */
      for ( i = 0 ; i < loc ; i++ )
      {
            q = q -> next ;
            /* if end of linked list is encountered */
            if ( q == NULL )
            {
                  printf ( "\nThere are less than %d elements", loc );
                  return ;
            }
      }
      /* insert new node */
      q = q -> prev ;
      temp = malloc ( sizeof ( dnode ) ) ;
      temp -> data = num ;
      temp -> prev = q ;
      temp -> next = q -> next ;
      temp -> next -> prev = temp ;
      q -> next = temp ;
}

/* displays the contents of the linked list */
void d_display ( dnode *q )
{
      printf ( "\n" ) ;

      /* traverse the entire linked list */
      while ( q != NULL )
      {
            printf ( "%2d\t", q -> data ) ;
            q = q -> next ;
      }
}

/* counts the number of nodes present in the linked list */
int d_count ( dnode * q )
{
      int c = 0 ;
      /* traverse the entire linked list */
      while ( q != NULL )
      {
            q = q -> next ;
            c++ ;
      }

      return c ;
}

/* deletes the specified node from the doubly linked list */
void d_delete ( dnode **s, int num )
{
      dnode *q = *s ;

      /* traverse the entire linked list */
      while ( q != NULL )
      {
            /* if node to be deleted is found */
            if ( q -> data == num )
            {
                  /* if node to be deleted is the first node */
                  if ( q == *s )
                  {
                        *s = ( *s ) -> next ;
                        ( *s ) -> prev = NULL ;
                  }
                  else
                  {
                        /* if node to be deleted is the last node */
                        if ( q -> next == NULL )
                              q -> prev -> next = NULL ;
                        else
                        /* if node to be deleted is any intermediate node */
                        {
                              q -> prev -> next = q -> next ;
                              q -> next -> prev = q -> prev ;
                        }
                        free ( q ) ;
                  }
                  return ;  /* return back after deletion */
            }
            q = q -> next ; /* go to next node */
      }
      printf ( "\n%d not found.", num ) ;

}
Bhanu Namikaze

Bhanu Namikaze is an Ethical Hacker, Web Developer, Student and Mechanical Engineer. He Enjoys writing articles, Blogging, Solving Errors and Social Networking. Feel Free to let me know any of your concerns about hacking or let me know if you need any more methods on hacking anything. Enjoy Learning

No comments:

Post a Comment