10. Doubly Linked List

  TITLE: DOUBLY LINKED LIST



// HEADER FILES
#include<stdio.h>
#include<conio.h>
//DECLARATION OF STRUCTURE
typedef struct node
{
char data ;
struct node *next,*prev ;
}node;
int main(void)  //MAIN STARTS
{
//DECLARATION OF FUNCTIONS
node *create(node *,char *);
void display(node *);
node *append(node *);
node *insert_by_val(node *,char);
node *insert_first(node *);
node *insert_by_pos(node*,int,int);
node *insert_by_pos_after(node*,int,int);
int count(node*);
node *delete_first(node *);
node *delete_by_val(node *,char);
node *delete_last(node*);
node *delete_by_pos(node*,int,int);
void reverse(node *,int);
//INITIALISATION OF VARIABLES
node *head=NULL,*p;
char st[10]={'\0'},val='\0',dval='\0';
int op=0,ps=0,c=0,dps=0,in=0,del=0;
clrscr();
head->prev=NULL;
printf("\n\nDoubly Linked list ");
do
{ //DO WHILE LOOP BEGINS
printf("\nSelect an operation\n===================");
printf("\n1.CREATE");
printf("\n2.DISPLAY");
printf("\n3.INSERT A NODE");
printf("\n4.DELETE A NODE");
printf("\n5.COUNT THE NUMBER OF NODES ");
printf("\n6.REVERSE");
printf("\nPRESS 0 TO EXIT \n");
scanf("%d",&op);
if(op==3)
{
printf("\nINSERT MENU\n");
printf("\n1.Append ");
printf("\n2.Insert a node at the beginnining ");
printf("\n3.Insert a node by value");
printf("\n4.Insert by position before the specified node");
printf("\n5.Insert by position after the specified node\n");
scanf("%d",&in);

}
else if(op==4)
{
printf("\nDELETE MENU\n");
printf("\n1.Delete first node");
printf("\n2.Delete a node by value");
printf("\n3.Delete last node");
printf("\n4.Delete by position\n");
scanf("%d",&del);

}
switch(op)  //SWITCH CASE
{
case 1 : printf("\nEnter the string\n");
flushall();
gets(st);
head=create(head,st);  //CALLING CREATE FUNCTION
break;
case 2 : display(head);      //CALLING DISPLAY FUNCTION
break;
case 3 : switch(in) //NESTED SWITCH CASE
{
case 1 : head=append(head);  //CALLING APPEND FUNCTION
printf("\n\nDisplaying the linked list with appended node");
display(head);
break;
case 2 : head=insert_first(head); //CALLING INSERT_FIRST FUNCTION
printf("\nthe new linked list\n ");
display(head);
break;
case 3 : printf("\nenter the data before which node is to be inserted => ");
flushall();
scanf("%c",&val);
head=insert_by_val(head,val);      //CALLING INSERT_BY_VAL FUNCTION
printf("\nThe new linked list is \n");
display(head);
break;
case 4 : printf("\nEnter the position for inserting the node : ");
scanf("%d",&ps);
c=count(head);
head=insert_by_pos(head,ps,c);           //CALLING INSERT_BY_POS FUNCTION
if(head!=NULL)
{
printf("\nThe new linked list => ");
display(head);
}
break;
case 5 : printf("\nEnter the position for inserting the node : ");
scanf("%d",&ps);
c=count(head);
head=insert_by_pos_after(head,ps,c);           //CALLING INSERT_BY_POS FUNCTION
if(head!=NULL)
{
printf("\nThe new linked list => ");
display(head);
}

}
break;
case 4 : switch(del)
{
case 1 : head=delete_first(head);           //CALLING DELETE_FIRST FUNCTION
printf("\nNode deleted ! ");
display(head);
break;
case 2 : printf("\nenter the data which is to be deleted => ");
flushall();
scanf("%c",&dval);
head=delete_by_val(head,dval);   //CALLING DELETE_BY_VAL FUNCTION
printf("\nNode deleted ! ");
printf("\nThe new linked list is \n");
display(head);
break;
case 3 : head=delete_last(head);       //CALLING DELETE_LAST FUNCTION
printf("\nNode deleted !");
display(head);
break;
case 4:  printf("\nEnter the position for the node : ");
scanf("%d",&dps);
c=count(head);
head=delete_by_pos(head,dps,c);     //CALLING DELETE_BY_POS FUNCTION
if(head!=NULL)
{
printf("\nThe new linked list => ");
display(head);
}
break;
}
break;
case 5 : c=count(head);        //CALLING COUNT FUNCTION
printf("\nThe number of nodes is %d",c);
break;

case 6 : c=count(head);
reverse(head,c);   //CALLING REVERSE FUNCTION
break;
default : printf("\nExiting program...");
}
}while(op<=6&&op!=0);
free(head); //TO FREE THE MEMORY ALLOCATED TO HEAD
free(p);
getch();
return 0;
}//END OF MAIN
//FUNCTION DEFINITIONS
node *create(node *head, char *str)
{
node *p,*q;
head=NULL;
head->prev=NULL;
while(*str!='\0')
{
if(head==NULL)
{
p=head=(node*)malloc(sizeof(node));
head->next=NULL;
head->prev=NULL;
}
else
{
q=p->next=(node*)malloc(sizeof(node));
p->next=q;
q->prev=p;
p=q;
}
p->data=*str;
p->next=NULL;
str++;
}
return head;
}
void display(node *head)
{
node *p=NULL;
p=head;
printf("\n\nThe linked list is \n");
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
}

node *append(node *head)
{
node *p=NULL;
p->prev=NULL;
p=head;
while(p->next!=NULL)
{
p=p->next;

}
p->next=(node*)malloc(sizeof(node));
p->next->prev=p;
p=p->next;
printf("\nEnter the data to be appended \n");
flushall();
scanf("%c",&p->data);
p->next=NULL;
return head;

}
node *insert_first(node *head)
{
node *p=NULL;
p->prev=NULL;
if(head==NULL)
{
printf("\n singly linked list is empty...");
}
else
{
p=(node*)malloc(sizeof(node));
p->prev=NULL;
printf("\nEnter the data => ");
flushall();
scanf("%c",&p->data);
p->next=head;
head=p;

}
return head;
}
node *insert_by_val(node *head,char n)
{
node *p=NULL,*q=NULL;
p->prev=NULL;
q->prev=NULL;
p=head;
if(p==NULL)
{
printf("\nThe linked list does not exist...\n");
}
else if(head->data==n)
{
head=insert_first(head);
}
else
{
while(p->next->data!=n)
{

p=p->next;
}
if(p->next->data==n)
{
q=(node*)malloc(sizeof(node));
q->prev=p;
printf("\nEnter the data : ");
flushall();
scanf("%c",&q->data);
q->next=p->next;
p->next=q;
}
else
printf("\nNo such data available...");

}
return head;
}
int count(node *head)
{
node *p=NULL;
int cnt=0;
p->prev=NULL;
p=head;
if(head==NULL)
{
return 0;
}
else
{
while(p!=NULL)
{
p=p->next;
cnt++;
}
return cnt;
}
}
node *insert_by_pos(node *head,int n,int c)
{
node *p=NULL,*q=NULL;
int i=0;
p->prev=NULL;
q->prev=NULL;
p=head;
if(n<=c)
{
if(head==NULL)
printf("\nThe linked list does no exist...");
else if(n==0)
printf("\ninvalid position...\n");
else if(n==1)
head=insert_first(head);
else
{
for(i=1;i<n-1;i++)
{
p=p->next;
}
q=(node*)malloc(sizeof(node));
printf("\nEnter the data : ");
flushall();
scanf("%c",&q->data);
q->next=p->next;
p->next=q;
q->prev=p;

}

}
else
printf("\nThe node cannot be inserted\n");
return head;
}
node *insert_by_pos_after(node *head,int n,int c)
{
node *p=NULL,*q=NULL;
int i=0;
p->prev=NULL;
q->prev=NULL;
p=head;
if(n<=c)
{
if(head==NULL)
printf("\nThe linked list does no exist...");
else if(n<0)
printf("\ninvalid position...\n");
else if(n==0)
head=insert_first(head);
else
{
for(i=0;i<n-1;i++)
{
p=p->next;
}
q=(node*)malloc(sizeof(node));
printf("\nEnter the data : ");
flushall();
scanf("%c",&q->data);
q->next=p->next;
p->next=q;
q->prev=p;

}

}
else
printf("\nThe node cannot be inserted\n");
return head;
}

node *delete_first(node *head)
{
node *p=NULL;
p->prev=NULL;
p=head;
if(head==NULL)
{
printf("\n singly linked list is empty...");
}
else
{
p=p->next;
head=p;
//head->next=p;
head->prev=NULL;

}
return head;
}
node *delete_by_val(node *head,char n)
{
node *p=NULL,*q;
p->prev=NULL;
p=head;
if(p==NULL)
{
printf("\nThe linked list does not exist...\n");
}
else if(head->data==n)
{
head=delete_first(head);
}
else
{
while(p->next->data!=n)
{
p=p->next;
}
if(p->next->data==n)
{
q=p->next;
p->next=q->next;
q->prev=p;
}
else
printf("\nNo such data available...");

}
return head;
}
node *delete_last(node *head)
{
node *p=NULL;
p->prev=NULL;
p=head;
while(p->next->next!=NULL)
{
p=p->next;

}
p->next=NULL;
return head;

}
void reverse(node *head,int cnt)
{
int i=0;
node *p=NULL;
p->prev=NULL;
while(cnt>0)
{
p=head;
for(i=1;i<cnt;i++)
{
p=p->next;

}
printf("\t%c",p->data);
cnt--;
}
}
node *delete_by_pos(node *head,int n,int c)
{
node *p=NULL,*q=NULL;
int i=0;
p->prev=NULL;
q->prev=NULL;
p=head;
if(n<=c)
{
if(head==NULL)
printf("\nThe linked list does no exist...");
else if(n==0)
printf("\ninvalid position...\n");
else if(n==1)
head=delete_first(head);
else
{
for(i=1;i<n-1;i++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
q->prev=p;

}

}
else
printf("\nThe node cannot be inserted\n");
return head;
}