♠ Posted by Unknown in C'Language,Data Structure at 11:26
Doubly Linked list Operations
A doubly linked list is defined as a collection of nodes. Each node has three parts.
1. Information
2. Pointer to previous node
3. Pointer to next node
Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.
Doubly linked list creation algorithm
Step 1 :
[Initilization]
1) Start. Next = null
2) Previous. Next = null
Step 2 : [Assign address of start variable to node]
Node = address of start
Step 3 : [Make left and right links of a node]
1) Next [node] = node [make link to node]
2) Previous [node] = node [make link to node]
3) Node = Next [node] [Move pointer to next node]
4) Info [node] = value [Information value of a node]
5) Next [node] = NULL [Assign NULL to the address field]
Step 4 : [ Call Step 3]
Repeat Step 3 to create required number of nodes for linked list
Step 5 : End .
Algorithm for traversing a doubly inked list
Step 1 : [initialization]
Node = start. Next [points to the first node in the list]
Step 2 : [Traverse the list in forward direction]
Repeat while Next [node] # NULL process Info [Node]
Step 3 : [Traverse the list in backward direction]
Repeat while Node # NULL Process Info [Node]
Step 4 : Exit.
Algorithm to insert a node at right of the right most node
Step 1 : [Initialization]
Node =Start
Step 2 :
[Create a new node]
New = Create a Node
Step 3 : [Read information associated with newly created node]
Info [Newly] = value
Step 4 : [Perform the insertion]
I) Next [new] = node
II) Previous [New] = Previous [node]
III) Next [Previous[node]] = New
IV) Next [Node] = New
Step 5 : Exit
Algorithm to delete right most node
Step 1 : [Initialization]
Node = Start
Step 2 : [Initialization counter]
Counter = 0
Step 3 : [check the list]
If Node = Null
Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
Repeat while Node # NULL
I) Node = Next [Node]
II) Counter = Counter + 1
Step 5 : [perform deletion]
Node = Start
Repeat through (II) while counter # 1
I) Node = Next [Node]
II) Counter = Counter – 1
III) Next [previous[node]] = Next [Node]
IV) Previous [Next [node]] = previous [node]
V) Delete (node)
Step 6 : Exit.
Algorithm to delete a desired node
Step 1 : [Initialization]
Node = Start
Step 2 : [Check the list]
If node =
NULL
Output
“underflow” and Exit
Step 3 : [Set the counter ]
Search = 0
Step 4 : [Input the node number to which you want to delete]
Node delete =
value
Step 5 : [Perform deletion]
Repeat while
Node # NULL
If Search =
Delete _Node
Next
[Previous [Node]] = Next [Node]
Previous
[Next[Node]] = Previous [Node]
Delete (Node)
Else
Node =
Next [node]
Search
= Search + 1
Step 6 : Exit
Example:
#include<stdio.h>
#include<malloc.h>
struct dnode
{
struct
dnode *prv;
int
data;
struct
dnode *next;
};
main()
{
struct
dnode *p;
int
ans;
p=NULL;
clrscr();
do
{
printf("\n1:enter
new node:\n");
printf("2:enter
new node at begining:\n");
printf("3:enter
new node at position:\n");
printf("4:display
value:\n");
printf("5:delete
node:\n");
printf("6:exit\n");
printf("enter
your choice :");
scanf("%d",&ans);
switch(ans)
{
case
1:
append(&p);
break;
case
2:
addatbeg(&p);
break;
case
3:
addatpos(&p);
break;
case
4:
display(p);
break;
case
5:
deletatpos(&p);
break;
case
6:
exit(0);
break;
}
}while(ans!=6);
getch();
return;
}
append(struct dnode **q)
{
struct
dnode *temp,*r;
int
n;
temp=(*q);
if(*q==NULL)
{
*q=(struct
dnode*)malloc(sizeof(struct dnode*));
(*q)->prv=NULL;
(*q)->next=NULL;
temp=(*q);
}
else
{
while(temp->next!=NULL)
temp=temp->next;
r=(struct
dnode*)malloc(sizeof(struct dnode));
temp->next=r;
r->prv=temp;
r->next=NULL;
temp=temp->next;
}
printf("Enter
value:");
scanf("%d",&n);
temp->data=n;
return;
}
addatbeg(struct dnode **q)
{
struct
dnode *temp;
int
n;
temp=(struct
dnode*)malloc(sizeof(struct dnode));
temp->prv=NULL;
temp->next=*q;
(*q)->prv=temp;
printf("Enter
value:\n");
scanf("%d",&n);
temp->data=n;
(*q)
= (*q)->prv;
return;
}
addatpos(struct dnode **q)
{
struct
dnode *temp;
int
pos,n,flag=0;
printf("Enter
position:\n");
scanf("%d",&pos);
while((*q)->next!=NULL)
{
if((*q)->data==pos)
{
flag=1;
break;
}
else
{
flag=0;
}
(*q)=(*q)->next;
}
if(flag==1)
{
printf("enter
value :");
scanf("%d",&n);
temp=(struct
dnode*)malloc(sizeof(struct dnode));
temp->prv=(*q)->prv->next;
(*q)->prv->next=temp;
temp->next=*q;
(*q)->prv=temp;
temp->data=n;
}
else
{
printf("element
is not available:\n");
}
return;
}
deletatpos(struct dnode **q)
{
struct
dnode *temp;
int
n;
printf("Enter
the position:\n");
scanf("%d",&n);
temp=*q;
while(temp->next!=NULL)
{
if(temp->data==n)
{
if(temp==*q)
{
(*q)=(*q)->next;
(*q)->prv=NULL;
}
else
{
if(temp->next==NULL)
temp->prv->next=NULL;
else
{
temp->prv->next=temp->next;
temp->next->prv=temp->prv;
free(temp);
}
}
}temp=temp->next;
}
return;
}
display(struct dnode *q)
{
while(q!=NULL)
{
printf("%d
",q->data);
q=q->next;
}
return;}
0 comments:
Post a Comment