Data structure doubly linked list programs

Data structure Doubly linked list programs

1. P a g e|1
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
/* Doubly Linked ListActs Like Stack */
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *llink;
int info;
struct node *rlink;
};
typedef struct node NODE;
void ins_first(NODE**, int);
int del_first(NODE**);
voiddisplay(NODE*);
int main()
{
NODE *first=NULL;
int choice, item;
for(;;)
{
printf("Operation Resarch On Doubly Linked List\n");
printf("Program Acts Like Stack\n");
printf("1.Push OR Insert Front\n");
printf("2.Pop OR Delete Front\n");
printf("3.Display\n");
printf("4.Exit\n");
printf("Enter U R Choice\n");
scanf("%d", &choice);
printf("\n\n");
switch(choice)
{
case 1 : printf("Enter The Item To Insert\n");
scanf("%d", &item);
printf("\n\n");
ins_first(&first, item);
break;
case 2 : item=del_first(&first);
if(item!='\0')
printf("Deleted Element Is %d\n\n", item);
break;
case 3 : printf("Contents Of Stack Are\n");
display(first);
break;
default : exit(0);
}
}
return 1;
}

2. P a g e|2
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
void ins_first(NODE **first, int item)
{
NODE *newn;
newn=(NODE*)malloc(sizeof(NODE));
newn->llink=NULL;
newn->info=item;
if(*first==NULL)
{
newn->rlink=NULL;
*first=newn;
}
else
{
newn->rlink=*first;
newn->rlink->llink=newn; /*HihglyIMP */
*first=newn;
}
}
int del_first(NODE **first)
{
int item;
NODE *temp;
if(*first==NULL)
{
printf("Stack IS Underflow\n\n");
return('\0');
}
temp=*first;
item=temp->info;
*first=temp->rlink; /* *first->llink=NULL Is An Error. */
free(temp);
return item;
}
void display(NODE *first)
{
NODE *temp;
temp=first;
if(first==NULL)
{
printf("Stack Is Empty\n\n");
}
else
{
while(temp->rlink!=NULL)
{
printf("%d\n", temp->info);
temp=temp->rlink;
}
printf("%d\n\n", temp->info);
}
}

3. P a g e|3
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
/*Doubly Linked List */
Insert Last
void ins_last(NODE **first, int item)
{
NODE *newn, *temp;
newn=(NODE*)malloc(sizeof(NODE));
newn->info=item;
newn->rlink=NULL;
if(*first==NULL)
{
newn->llink=NULL;
*first=newn;
}
else
{
temp=*first;
while(temp->rlink!=NULL)
temp=temp->rlink;
newn->llink=temp;
temp->rlink=newn;
}
}

4. P a g e|4
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
/* Doubly Linked List */
Delete Last
int del_last(NODE**first)
{
int item;
NODE *temp;
if(*first==NULL)
{
printf("DLL IS Empty\n\n");
return('\0');
}
else
{
temp=*first;
if(temp->rlink==NULL)
{
item=temp->info;
*first=NULL;
free(temp);
return item;
}
else
{
while(temp->rlink!=NULL)
temp=temp->rlink;
item=temp->info;
temp->llink->rlink=NULL;
free(temp);
return item;
}
}
}

5. P a g e|5
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
Write A C Module To Find The Frequency Of Given Element x In A DLL.

6. P a g e|6
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
WAP To Search A Node With A Given Data With A DLL, If It IsFound Delete It, Otherwise Display Appropriate
Message.
int del_k(NODE **first, int k)
{
int item;
NODE *temp;
if(*first==NULL)
{
printf("DLL IS Empty\n\n");
return('\0');
}
temp=*first;
if(temp->rlink==NULL &&temp->info==k)//Element Found In 1
st
Position No Further Element Present Right To It.
{
item=temp->info;
*first=NULL;
free(temp);
return item;
}
if(temp->rlink!=NULL && temp->info==k) //Element Found In 1
st
Position Further Element Present Right To It.
{
item=temp->info;
*first=temp->rlink;
temp->rlink->llink=NULL;
free(temp);
return item;
}
while(temp!=NULL)
{
if(temp->info==k)
break;
temp=temp->rlink;
}
if(temp!=NULL)
{
item=temp->info;
temp->llink->rlink=temp->rlink;
if(temp->rlink!=NULL) /* If Element Found In Middle & Further Element Present Right To It */
temp->rlink->llink=temp->llink;
free(temp);
return item;
}
else
{
printf("k=%d Not Found\n", k);
return('\0');
}
}

7. P a g e|7
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
Dec 05
WAPTo Perform The Following Operations On Doubly Linked List.
1)To Insert A Node To The Right Of AGiven Node.
2)To Delete A Node On The Left Of A Given Node. 12 Marks.
1)To Insert A Node To The Right Of A Given Node.
void ins_x_right_to_y(NODE **first, int x, int y)
{
NODE *newn, *temp;
newn=(NODE*)malloc(sizeof(NODE));
newn->info=x;
if(*first==NULL)
printf("List Is Empty\n");
else
{
temp=*first;
if(temp->info==y && temp->rlink==NULL)
{
newn->rlink=NULL;
newn->llink=temp;
temp->rlink=newn;
}
else
{
while(temp!=NULL)
{
if(temp->info==y)
break;
temp=temp->rlink;
}
if(temp!=NULL && temp->rlink!=NULL)
{
newn->llink=temp->rlink->llink;
newn->rlink=temp->rlink;
temp->rlink->llink=newn;
temp->rlink=newn;
}
else if(temp!=NULL && temp->rlink==NULL)
{
newn->rlink=NULL;
newn->llink=temp;
temp->rlink=newn;
}
else
printf("y=%d Not Found In The List\n", y);
}
}
}

8. P a g e|8
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
2)To Delete A Node On The Left Of A Given Node.
int del_x_left_to_y(NODE **first, int y)
{
int item;
NODE *temp, *arc;
if(*first==NULL)
{
printf("DLL IS Empty\n\n");
return('\0');
}
temp=*first;
while(temp!=NULL)
{
if(temp->info==y)
break;
temp=temp->rlink;
}
if(temp!=NULL && temp->llink!=NULL)
{
arc=temp->llink;
item=arc->info;
if(arc->llink!=NULL)
{
arc->llink->rlink=arc->rlink;
temp->llink=arc->llink;
}
else /* 1213 14 if y=13, To Delete 12 */
{
temp->llink=NULL;
*first=arc->rlink;
}
free(arc);
return item;
}
else if(temp!=NULL && temp->llink==NULL)
{
printf("No Item Present Left To It So Deletion Not Possible");
return('\0');
}
else
{
printf("y=%d Not Found\n");
return('\0');
}
}

9. P a g e|9
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
To Insert A Node On The Left Of A Given Node.
void ins_x_left_to_y(NODE **first, int x, int y)
{
NODE *newn, *temp;
newn=(NODE*)malloc(sizeof(NODE));
newn->info=x;
if(*first==NULL)
printf("List Is Empty\n");
else
{
temp=*first;
if(temp->info==y)
{
newn->llink=NULL;
newn->rlink=*first;
temp->llink=newn;
*first=newn;
}
else
{
while(temp!=NULL)
{
if(temp->info==y)
break;
temp=temp->rlink;
}
if(temp!=NULL)
{
newn->llink=temp->llink;
newn->rlink=temp;
temp->llink->rlink=newn;
temp->llink=newn;
}
else
printf("y=%d Not Found In The List\n", y);
}
}
}

10. P a g e|10
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
To Delete A Node On The Right Of A Given Node.
int del_x_right_to_y(NODE **first, int y)
{
int item;
NODE *temp, *arc;
if(*first==NULL)
{
printf("DLL IS Empty\n\n");
return('\0');
}
temp=*first;
while(temp!=NULL)
{
if(temp->info==y)
break;
temp=temp->rlink;
}
if(temp!=NULL && temp->rlink!=NULL)
{
arc=temp->rlink;
item=arc->info;
temp->rlink=arc->rlink;
if(arc->rlink!=NULL) /* 12,6 13, 14 if y=13 To Delete 14 It's Required */
arc->rlink->llink=arc->llink;
free(arc);
return item;
}
else if(temp!=NULL&& temp->rlink==NULL)
{
printf("No Item Present Right To It, So Deletion Not Possible\n");
return('\0');
}
else
{
printf("y=%d Not Found\n", y);
return('\0');
}
}

11. P a g e|11
Ashoka R, 2
nd
Sem, Maharaja Institute Of Technology Mysore.
Dec 06/Jan 07
WAP ToInterchange The Mth And Nth Elements Of A DLL. 10Marks