Description : In this program we have to create a doubly
linked list, insert the elements in to a doubly linked list, delete the
elements from that list and finally perform the traversal operation
ALGORITHM :
Step 1: Start
Step 2: Declare a
structure with *next, *pre
Step 3: Declare
*start, *new ,*l as structure pointers
Step 4: Print main
menu
Step 5: Read
choice
Step 6: Switch
choice
6.1: call insert function if
choice==1
6.2: call delete function if
choice==2
6.3: call view function if choice==3
Step 7: Stop
Step 8: Start of
insert function
Step 9: Read e
Step 10: If
start==null
Step 11: Create a
new node
Step 12:
Start->data=e
Step 13:
Start->next=null
Step 14:
Start->pre=null
Step 15: read
choice, where to insert
Step 16: if
choice==1
Step 16.1: Create a new mode
Step
16.2: new -> data=e
Step 16.3: new -> next=start
Step 16.4: start->pre=new
Step 16.5:
new->pre=null
Step 16.6:
Start->new
Step 17: otherwise if choice==2
17.1: read position p
17.2: l=start
17.3: while i<(p-1)
17.4: incrent i
17.5: l=l->next
17.6: new -> data =e
17.7: new -> pre=l
17.8: new->next=new
17.9: l-> next=new
17.10: l->next->pre=new
Step 18: if
choice==3
18.1: l=start
18.2: while l->next!=null
18.3: l=l->next
18.4: create a new mode
18.5: new->data=e
18.6: new->next=null
18.7: l->next=new
18.8: new->pre=l
Step19: end of
insert function
Step20: start of
deletion function
Step21: write menu
Step22: read
choice
Step23: if
choice==1
23.1: temp=start->data
23.2: start=start->next
23.3: start->pre=null
Step24: if
choice==2
24.1: read position
24.2: l=start
24.3: while (i=1 <p-1)
24.4: l=l->next
24.5: increment I by 1
24.6: temp=l-next->data
24.7: l->next=l->next->next
24.8: l->next->pre=l
Step25: if
choice==3
25.1: read l=start
25.2: while l->next->next!=
null
25.3: l=l->next
25.4: temp=l->next->data
25.5: l->next=null
Step26: end of
delete function
Step27: start of
view function
Step28: read
choice
Step29: if
choice==1
29.1: l=next
29.2: while (l->next!= null)
29.3: write l-> data,
l=l->next
29.4: write l->data
Step30: if
choice==2
30.1: l=start
30.2: while l!=start
30.3: write l->data
30.4: l=l->pre
30.5: write l->data
Step31: end of
function view
Program:
#include<stdio.h>
#include<malloc.h>
/* START OF STRUCTURE DEFINITION */
struct link
{
int data;
struct link *next;
struct link *prev;
}*start,*new,*temp,*l,*l1,*t,*start1;
/* END OF STRUCTURE DEFINITION */
int item,ch,i,j,p,n;
/* VARIABLE DECLARATION */
/* START OF MAIN FUNCTION */
main()
{
start=NULL;
start1=NULL;
clrscr();
printf(" **** MENU ****");
printf("\n1.Insertion\n2.Deletion\n3.Traverse\n4.search\n5.sort\n6.merge\n7.reverse\n8.exit\n");
while(1)
{
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:display();
break;
case 4:search();
break;
case 5:sort();
break;
case 6:merge();
break;
case 7:reverse();
break;
case 8:exit();
}
}
getch();
}
/* END OF MAIN FUNCTION */
/* START OF INSERT FUNCTION */
insert()
{
l=start;
printf("enter an item to be
inserted:");
scanf("%d",&item);
new=malloc(sizeof(struct link));
new->data=item;
if(start==NULL)
{
new->prev=NULL;
new->next=NULL;
start=new;
}
else
{
printf("1.start\n2.middle\n3.end\n");
printf("enter the place to insert
item:");
scanf("%d",&ch);
if(ch==1)
{
new->next=start;
new->prev=NULL;
start=new;
}
if(ch==2)
{
printf("enter
the position to place item:");
scanf("%d",&p);
for(i=1;i<p-1;i++)
l=l->next;
new->prev=l;
new->next=l->next;
l->next=new;
}
if(ch==3)
{
while(l->next!=NULL)
l=l->next;
new->prev=l;
new->next=NULL;
l->next=new;
}
}
}
/* END OF INSERT FUNCTION */
/* START OF DELETE FUNCTION */
delete()
{
l=start;
if(start==NULL)
printf("*** LIST IS EMPTY ***");
else
{
printf("1.start\n2.middle\n3.end");
printf("enter the place to delete the
item:");
scanf("%d",&ch);
if(ch==1)
{
item=start->data;
printf("deleted item is
:%d",item);
start=start->next;
start->prev=NULL;
}
if(ch==2)
{
printf("enter the position to delete
an item:");
scanf("%d",&p);
if(l->next==NULL)
{
item=l->data;
printf("deleted item
is:%d",item);
l=start=NULL;
}
else
{
for(i=1;i<p-1;i++)
l=l->next;
item=l->next->data;
printf("deleted item
is:%d",item);
l->next=l->next->next;
l->next->prev=l;
}
}
if(ch==3)
{
if(l->next==NULL)
{
item=l->data;
printf("deleted item is
:%d",item);
l->prev=NULL;
l=start=NULL;
}
else
{
while(l->next->next!=NULL)
l=l->next;
item=l->next->data;
printf("deleted item
is:%d",item);
l->next=NULL;
}
}
}
}
/* END OF DELETE FUNCTION */
/* START OF DISPLAY FUNCTION */
display()
{
if(start==NULL)
printf("*** LIST IS EMPTY
***\n");
else
{
for(l=start;l->next!=NULL;l=l->next)
if(l==start)
printf("\nstart:%d",l->data);
else
printf("\n %8d",l->data);
if(l->next==NULL)
printf("\n last:%d",l->data);
}
}
/* END OF DISPLAY FUNCTION */
/* START OF SEARCH FUNCTION */
search()
{
int f=0;
if(start==NULL)
printf(" *** LIST IS EMPTY ***
");
else
{
printf("enter the search
item:");
scanf("%d",&item);
for(l=start,i=1;l!=NULL;l=l->next,i++)
if(item==l->data)
{
f=1;
break;
}
if(f==1)
printf("item %d found at position
%d",item,i);
else
printf("item %d not found in
list",item);
}
}
/* END OF SEARCH FUNCTION */
/* START OF SORT FUNCTION */
sort()
{
int t;
if(start==NULL)
printf(" *** LIST IS EMPTY ***
");
else
{
for(l1=start;l1->next!=NULL;l1=l1->next)
for(l=start;l->next!=NULL;l=l->next)
if(l->data > l->next->data)
{
t=l->next->data;
l->next->data=l->data;
l->data=t;
}
printf("THE SORTED ORDER IS:");
for(l=start;l!=NULL;l=l->next)
printf("%3d",l->data);
}
printf("\n");
}
/* END OF SORT FUNCTION */
/* START OF MERGE FUNCTION */
merge()
{
printf("enter number items to be
inserted in second list:");
scanf("%d",&n);
for(j=1;j<=n;j++)
{
l1=start1;
printf("enter an item:");
scanf("%d",&item);
new=malloc(sizeof(struct link));
new->data=item;
if(start1==NULL)
{
new->prev=NULL;
new->next=NULL;
start1=new;
}
else
{
printf("1.start\n2.middle\n3.end\n");
printf("enter the place to insert
item:");
scanf("%d",&ch);
if(ch==1)
{
new->next=start1;
new->prev=NULL;
start1=new;
}
if(ch==2)
{
printf("enter the position to place
item:");
scanf("%d",&p);
for(i=1;i<p-1;i++)
l1=l1->next;
new->prev=l1;
new->next=l1->next;
l1->next=new;
}
if(ch==3)
{
while(l1->next!=NULL)
l1=l1->next;
new->prev=l1;
new->next=NULL;
l1->next=new;
}
}
}
if(start==NULL)
start=start1;
else
{
l=start;
while(l->next!=NULL)
l=l->next;
for(l1=start1;l1->next!=NULL;l1=l1->next)
{
l->next=l1;
l=l->next;
}
}
printf(" *** LIST IS MERGED ***
\n");
}
/* END OF MERGE FUNCTION */
/* START OF REVERSE FUNCTION */
reverse()
{
if(start==NULL)
printf(" *** LIST IS EMPTY ***\n
");
else
{
l=start;
l1=t=NULL;
while(l!=NULL)
{
l1=t;
t=l;
l=l->next;
t->next=l1;
}
start=t;
printf(" *** LIST IS REVERSED *** \n");
}
}
/* END OF REVERSE FUNCTION */
Input/Output:
**** MENU ****
1.Insertion
2.Deletion
3.Traverse
4.search
5.sort
6.merge
7.reverse
8.exit
enter your choice:1
enter an item to be inserted:10
enter your choice:1
enter an item to be inserted:20
1.start
2.middle
3.end
enter the place to insert item:1
enter your choice:1
enter an item to be inserted:30
1.start
2.middle
3.end
enter the place to insert item:3
enter your choice:1
enter an item to be inserted:40
1.start
2.middle
3.end
enter the place to insert item:2
enter the position to place item:3
enter your choice:1
enter an item to be inserted:50
1.start
2.middle
3.end
enter the place to insert item:2
enter the position to place item:2
enter your choice:3
start: 20
50
10
40
last: 30
enter your choice:6
enter number items to be inserted
in second list:3
enter an item:60
enter an item:70
1.start
2.middle
3.end
enter the place to insert item:3
enter an item:80
1.start
2.middle
3.end
enter the place to insert item:1
*** LIST IS MERGED ***
enter your choice:3
start:20
50
10
40
30
80
60
last:70
enter your choice:4
enter the search item:80
item 80 found at position 6
enter your choice:4
enter the search item:10
item 10 found at position 3
enter your choice:7
*** LIST IS REVERSED ***
enter your choice:3
start:70
60
80
30
40
10
50
last: 20
enter your choice:5
THE SORTED ORDER IS: 10 20 30 40 50
60 70 80
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:1
deleted item is :10
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:3
deleted item is:80
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete an
item:3
deleted item is:40
enter your choice:3
start:20
30
50
60
last: 70
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete an
item:4
deleted item is:60
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:4
enter your choice:3
start:20
30
50
last: 70
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete an
item:3
deleted item is:50
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete an
item:3
deleted item is:50
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete an
item:1
deleted item is:30
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the item:1
deleted item is :20
enter your choice:3
last:70
enter your choice:2
1.start
2.middle
3.end
enter the place to delete the
item:1
deleted item is :70
enter your choice:3
*** LIST IS EMPTY ***
enter your choice:2
*** LIST IS EMPTY ***
enter your choice:8
conclusion: the program is error free
VIVA QUESATIONS:
1) List out the ypes of linked lists ?
Ans: i) circular linked lists ii) doubly linked lists, iii) circular doubly
linked list
2) What are the various operations
performed on the linked lists ?
Ans: i) creating a list, ii)
traversing the list iii) inserting an item etc..,
3) Another name for doubly linked
list ?
Ans: two-way linked list.
No comments:
Post a Comment