Help debug this doubly linked list

A

Abhinand

Disciple
I implemented doubly linked list using the following program in C but the create function is not working as intended. strangely the insert functions work great.

if i create a list with more than two values and display it it enters an infinite loop.
Code: 
#include <stdio.h>

#include <stdlib.h>

struct dll

{

  int ele;

  struct dll *right;

  struct dll *left;

}*head,*last;

int empty=1,in=0;

void create(void);

void display(void);

int find(int key);

void insfirst(void);

void inslast(void);

void insmid(void);

void delete(void);

int main(void)

{

  

  

  int data,ch,ch2;

  while(1)

  {

    printf("\n1.Create\n2.Insert\n3.Display\n4.Find\n5.Delete\n6.Exit");

    printf("\nEnter choice:");

    scanf("%d",&ch);

    

    switch(ch)

    {

      case 1:create();

             break;

      case 2:printf("1.Insert first\n2.Insert Middle\n3.Insert last\n");

             scanf("%d",&ch2);

             if(ch2==1)

             insfirst();

             if(ch2==2)

             insmid();

             if(ch2==3)

             inslast();

             break;

      case 3:display();

             break;

      case 4:printf("Enter Data:");

             scanf("%d",&data);

             find(data);

             break;

      case 5:delete();

             break;

      case 6:return 0;

      }

    }

}

void create(void)

{ 

  int ch;

  int key;

  struct dll *tmp;

  tmp=(struct dll *)malloc(sizeof(struct dll));

  

  while(1)

  {

    printf("Enter the data:");

    scanf("%i",&key);

    tmp->ele=key;

    if(head==NULL)

    { tmp->right=NULL;

      tmp->left=NULL;

      head=tmp;

      last=head;

      empty=0;

     }

     else

     { 

       tmp->right=NULL;

       tmp->left=last;

       last->right=tmp;

       last=tmp;

     }

     

     printf("Continue? [1/0]");

     scanf("%d",&ch);

     if(ch==0)

     break;

    

   }

   

}

void display(void)

{

 struct dll *tmp;

  

  for( tmp=head;tmp!=NULL;tmp=tmp->right)

  {

    printf("%d\t",tmp->ele);

    

   }

}

int find(int key)

{ struct dll *tmp;

  for(tmp=head;tmp!=NULL;tmp=tmp->right)

  { in++;

    if(tmp->ele==key)

    {

      printf("Found in %d pos",in);

      in=0;

      return 0;

    }

   }

 printf("Not found");

 return -1;

}

void inslast(void)

{  

   struct dll *tmp;

   tmp=(struct dll*)malloc(sizeof(struct dll));

   

   printf("Enter the data:");

   scanf("%d",&tmp->ele);

   

   last->right=tmp;

   tmp->left=last;

   tmp->right=NULL;

   last=tmp;

}

void insfirst(void)

{  struct dll *tmp;

   tmp=(struct dll*)malloc(sizeof(struct dll));

   

   printf("Enter the data:");

   scanf("%d",&tmp->ele);

   

   head->left=tmp;

   tmp->right=head;

   tmp->left=NULL;

   head=tmp;

}

void insmid(void)

{  struct dll *tmp1,*pos,*tmp2;

   tmp1=(struct dll*)malloc(sizeof(struct dll));

   tmp2=(struct dll*)malloc(sizeof(struct dll));

   pos=(struct dll*)malloc(sizeof(struct dll));

   int num;

   printf("Enter after which element");

   scanf("%d",&num);

   pos=head;

   while(pos!=NULL)

   {

     if(pos->ele==num)

     break;

     

     pos=pos->right;

   }

   

   if(pos!=NULL)

   { 

     printf("Enter the data:");

     scanf("%d",&tmp1->ele);

     tmp1->right=pos->right;

     tmp2=pos->right;

     pos->right=tmp1;

     tmp1->left=pos;

     tmp2->left=tmp1;

     

     }

     else 

     printf("Element not found");

     

}

void delete(void)

{ 

  struct dll *tmp1,*pos,*tmp2;

  tmp1=(struct dll*)malloc(sizeof(struct dll));

  pos=(struct dll*)malloc(sizeof(struct dll));

  tmp2=(struct dll*)malloc(sizeof(struct dll));

  int ele;

  printf("Enter the element to be deleted:");

  scanf("%d",&ele);

  pos=head;

   while(pos!=NULL)

   {

     if(pos->ele==ele)

     break;

     

     pos=pos->right;

   }

   

   if(pos!=NULL)

   {

     tmp1=pos->left;

     tmp2=pos->right;

     if(tmp1!=NULL)  //not first ele

     tmp1->right=tmp2;

     else if(tmp1==NULL)

     head=tmp2;

     if(tmp2!=NULL)   //not last ele

       tmp2->left=tmp1;

     else if(tmp2==NULL)

       last=tmp1;

     

     free(pos);

    }

   else

   printf("Element not found");

}

i've been struggling on this for days....please help guys
 
My C skills are a bit rusty but if I got it right, when you assign

last->right = tmp;

in else part inside create() you're assigning

tmp->right = tmp;

as last points to tmp. So, tmp->right = NULL in the else part inside create() has no effect. So display() loops infinitely.

Give it a thought.
 
agn said:
My C skills are a bit rusty but if I got it right, when you assign

last->right = tmp;

in else part inside create() you're assigning

tmp->right = tmp;

as last points to tmp. So, tmp->right = NULL in the else part inside create() has no effect. So display() loops infinitely.

Give it a thought.
Click to expand...
that assignment is correct.

the problem lies in the create() function.
you have kept an option of having multiple entries added while creating which is working correctly but you are not allocating (MALLOC) memory for every entry. Since you are using the same memory for multiple entries, in the end the "doubly link list" that is created is like this

head->left = head;
head->right = head;

hence the infinite loop.

there are a lot of other errors

no empty list checking in insfirst() and inslast()
a lot of unwanted "malloc" calls. in insmid() and delete()
memory allocated using "malloc" is not freed on program exit. You have to be a lot more careful when using malloc.
 
Back
Top