clinkl.c

right threaded binary tree

/* doubly linked list */

#include<stdio.h>
#include<conio.h>

typedef struct node1
{
  int info;
  struct node1 *prev;
  struct node1 *next;
}node;

/*creating queue*/
void crtl(node **d)
{
 *d=NULL;
}

/*insertion of element at beginning*/
void addatbeg(node **d)
{
  int item;
  node *temp,*temp1;
  temp = (node *) malloc (sizeof(node));
  if(temp==NULL)
  {
    printf("no space for allocation \n");
    return;
  }
  printf("element : ");
  scanf("%d",&item);
  temp->info = item;
  temp->prev=temp->next=temp;
  if(*d==NULL)
    *d=temp;
  else
  {
    temp1=*d;
    temp->next=*d;
    while(temp1->next!=*d)
      temp1=temp1->next;
    temp1->next=temp;
    temp->prev=temp1;
    *d=temp;
  }
}

/*insertion of element at end*/
void addatend(node **d)
{
  int item;
  node *temp,*temp1;
  temp = (node *) malloc (sizeof(node));
  if(temp==NULL)
  {
    printf("no space for allocation \n");
    return;
  }
  printf("element : ");
  scanf("%d",&item);
  temp->info = item;
  temp->prev=temp->next=temp;
  if(*d==NULL)
    *d=temp;
  else
  {
   temp1=*d;
   while(temp1->next!=*d)
       temp1=temp1->next;
   temp1->next=temp;
   temp->prev=temp1;
   temp->next=*d;
   (*d)->prev=temp;
  }
}

/*insertion of element at a particular position*/
void addatp(node **d)
{
 int item,pos,c=1;
 node *temp,*temp1;
 temp=(node *) malloc(sizeof(node));
 if(temp==NULL)
 {
  printf("no space for allocation \n");
  return;
 }
 printf("position : ");
 scanf("%d",&pos);
 if(pos<=count(d)+1)
 {
    if(pos==1)
      addatbeg(d);
    else
      if(pos==count(d)+1)
	 addatend(d);
      else
      {
	 printf("element : ");
	 scanf("%d",&item);
	 temp->info=item;
	 temp->prev=temp->next=NULL;
	 if(*d==NULL)
	    *d = temp;
	 else
	 {
	     temp1=*d;
	     if(pos<=count(d))
		while(c!=pos-1)
		{
		  temp1=temp1->next;
		  c++;
		}
		temp1->next->prev=temp;
		temp->next=temp1->next;
		temp1->next=temp;
		temp->prev=temp1;
	  }
      }
  }
  else
    printf("position out of range \n");
}

/* deletion of element at beginning*/
int delatbeg(node **d)
{
  int data;
  node *temp,*temp1;
  temp=temp1=*d;
  if(temp==NULL)
  {
   printf("doubly linked list is empty\n");
   return NULL;
  }
  data = temp->info;
  if(temp->next==temp)
    *d=NULL;
  else
  {
    while(temp1->next!=*d)
      temp1=temp1->next;
    temp1->next=temp->next;
    *d=temp->next;
  }
  free(temp);
  return data;
}

/* deletion of element at end */
int delatend(node **d)
{
  int data;
  node *temp=*d;
  if(temp==NULL)
  {
   printf("doubly linked list is empty\n");
   return NULL;
  }
  if(temp->next==temp)
    *d=NULL;
  else
  {
    while(temp->next!=*d)
     temp=temp->next;
    temp->prev->next=*d;
  }
  data = temp->info;
  free(temp);
  return data;
}

/*deletion of element at a particular position*/
int delatp(node **d)
{
 int item,pos,c=1;
 node *temp=*d;
 if(*d==NULL)
  {
    printf("doubly linked list is empty \n");
    return NULL;
  }
 printf("position : ");
 scanf("%d",&pos);
 if(pos<=count(d))
 {
    if(pos==count(d))
       item=delatend(d);
    else
    if(pos==1)
       item=delatbeg(d);
    else
    {
      temp=*d;
      if(pos<count(d))
      {
       while(c!=pos)
       {
	  temp=temp->next;
	  c++;
       }
       temp->prev->next=temp->next;
       temp->next->prev=temp->prev;
       item=temp->info;
       free(temp);
      }
    }
  }
  else
  {
    printf("position out of range \n");
    return NULL;
  }
 return item;
}

/*display dll elements*/
void display(node **d)
{
  node *temp;
  temp=*d;
  if(temp==NULL)
  {
   printf("doubly linked list is empty \n");
   return;
  }
  else
  {
   printf("list : \n");
   do
   {
    printf("%d \t",temp->info);
    temp=temp->next;
   }
   while(temp!=*d);
   printf("\n");
  }
}

/*counts the no.of elements in doubly linked list*/
int count(node **d)
{
 int c=0;
 node *temp=*d;
 do
 {
  c++;
  temp=temp->next;
 }
 while(temp!=*d);
 return c;
}