C LANGUAGE BOOK |
Doubly linked list:-in this we use two pointer.
Previous Pointer and next Pointer
this help in traversing the list in forward and backward direction.
the node has three field
data
Previous Pointer
and next Pointer
struct me
{
int data;
struct me *next;
struct me *prev;
};
traversing the linked list.
Moving through a Doubly linked list is same as singly linked list but in this case
you can traverse it in either direction.
check list is not empty.
To traverse a linked list in forward direction.
you create a pointer and set it to head.
we move through the list node one by one until we encounter first null.
To traverse a linked list in backward direction.
go to last node.
now move through node to previous node using previous pointer until you first encounter null.
Note:on other operation:-you have to set two pointer.
Next pointer and Previous Pointer
Adding nodes to a linked list
Adding nodes to a linked list is relatively easy. We will need to cover the different cases of adding at the beginning, the middle or the end.
adding at the beginning:-
if list is empty.
create a temporary node assign data.
set its next pointer of temporary node to point to null.
set its Previous pointer of temporary node to point to null.
set head pointer of list to point to temporary node.
if list is not empty.
create a temporary node assign data.
set its next pointer of temporary node to point to starting node.
set its Previous pointer of temporary node to point to null.
set head pointer of list to point to temporary node.
adding at the middle of the linked list specified by Position:-
check List is not Empty
check list is not short.and position exist.
create a temporary node assign data.
go the poistion specified.
set the next pointer of temporary node to point to next node specified by position.
set the Previous pointer of temporary node to point to Previous node specified by position.
set the next pointer of Previous node to point to temporary node specified by position.
set the Previous pointer of next node to point to temporary node specified by position.
adding at the End:-
if list is empty.
create a temporary node assign data.
set its next pointer of temporary node to point to null.
set its Previous pointer of temporary node to point to null.
set head pointer of list to point to temporary node.
if list is not empty.
create a temporary node assign data.
set its next pointer of temporary node to point to null.
go to the last node of list.
set its Previous pointer of temporary node to point to last node.
set next pointer of last node to point to temporary node.
deleting at the beginning:-
check list is not empty.
if there is one node
free the node.
if there is more than one node.
create a temporary node assign starting node.
set its Previous pointer of next node of starting node to point to null.
go to last node.set the next pointer of last node to point to next node of starting node.
free temporary node.
deleting at the middle of the Doubly linked list specified by Position:-
check List is not Empty
check list is not short.and position exist.
go the position specified.
create a temporary node assign node specified by position
set the next pointer of Previous node to point to next node of node specified by position.
set the Previous pointer of next node of node to point to Previous node of node specified by position.
set the next pointer of temporary node to point to null.
set the Previous pointer of next node to point to null.
free the temporary node.
deleting at the End:-
check list is not empty.
if there is one node
free the node.
if there is more than one node.
go to previous node of last node.
create a temporary node assign last node.
set its next pointer of previous node of last node to point to null.
set its Previous pointer of last node to point to null.
free temporary node.
/*WAP to Perform Doubly Linked List Operation */
#include<alloc.h>
#include<stdio.h>
struct me
{
int data;
struct me *next;
struct me *prev;
};
void main()
{
struct me *p;
int j,m,n;
do
{
printf("\n\tDOUBLYLINKEDLIST");
printf("\n\t1.INSERTION");
printf("\n\t2.DELETION");
printf("\n\t3.SORTING");
printf("\n\t4.DISPLAY AS NORMAL ORDER");
printf("\n\t5.DISPLAY AS REVERSE ORDER");
printf("\n\t6.EXIT\n");
printf("\n\tWHAT DO YOU WANT TO DO(PRESS 1 TO 6): ");
scanf("%d", &j);
switch(j)
{
case 1: Insertion(&p);
break;
case 2: Deletion(&p);
break;
case 3: Sorting(&p);
printf("\n");
break;
case 4: DisplayN(p);
printf("\n");
break;
case 5: DisplayR(p);
printf("\n");
break;
case 6: exit(1);
default : err_msg(3);
}
}while(j>=1 && j<=6);
}
Insertion(struct me **q)
{
int i,m,n;
int ch;
do
{
printf("\n\tINSERTION");
printf("\n\t1.INSERT AT BEGINNING");
printf("\n\t2.INSERT AT POSITION");
printf("\n\t3.INSERT AT END");
printf("\n\t4.RETURN\n");
printf("\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
scanf("%d",&i);
switch(i)
{
case 1: printf("\n\tENTER THE NUMBER : ");
scanf("%d", &m);
AddAtBeg(&(*q),m);
printf("\n");
break;
case 2: printf("\n\tENTER THE NUMBER : ");
scanf("%d", &m);
printf("\tENTER THE POSITION : ");
scanf("%d", &n);
AddAtPos(*q , m, n);
printf("\n");
break;
case 3: printf("\n\tENTER THE NUMBER : ");
scanf("%d", &m);
AddAtEnd(&(*q) , m);
printf("\n");
break;
case 4: return;
default : err_msg(3);
}
}while(i>=1 && i<=4);
}
Deletion(struct me **q)
{
int i,m,n;
do
{
printf("\n\tDELETION");
printf("\n\t1.DELETE AT BEGINNING");
printf("\n\t2.DELETE AT POSITION");
printf("\n\t3.DELETE AT END");
printf("\n\t4.RETURN\n");
printf("\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
scanf("%d", &i);
switch(i)
{
case 1: DeleteAtBeg(&(*q));
printf("\n");
break;
case 2: printf("\n\tENTER THE POSITION : ");
scanf("%d", &n);
DeleteAtPos(*q ,n);
printf("\n");
break;
case 3: DeleteAtEnd(&(*q));
printf("\n");
break;
case 4: return;
default : err_msg(3);
}
}while(i>=1 && i<=4);
}
Sorting(struct me **q)
{
int i;
do
{
printf("\n\tSORTING");
printf("\n\t1.USING SELECTION SORT");
printf("\n\t2.RETURN");
printf("\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 2): ");
scanf("%d", &i);
switch(i)
{
case 1: UsingSelectionSort(&(*q));
printf("\n");
break;
case 2: return;
default : err_msg(3);
}
}while(i>=1 && i<=2);
}
AddAtBeg(struct me **q,int x)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
w = malloc(sizeof(struct me));
w->data = x;
w->prev = NULL;
w->next = NULL;
*q = w;
}
else
{
w = malloc(sizeof(struct me));
w->data = x;
w->prev = p->prev;
p->prev = w;
w->next = *q;
*q = w;
err_msg(2);
}
return;
}
AddAtPos(struct me *q,int x,int y)
{
struct me *p,*w,*z;
int i;
w = q;
z = q;
if(w == NULL)
{
err_msg(5);
return;
}
for(i = 0; i < y; i++)
{
z = z->next;
if(z == NULL)
{
printf("\tCANNOT INSERT THERE ARE LESS THAN");
printf("\n\t%d ELEMENTS IN THE LIST", y);
return;
}
}
{
printf("\tHEELLOIOYUO");
p = malloc(sizeof(struct me));
p->data = x;
p->prev = z;
p->next = z->next;
z->next->prev = p;
z->next = p;
}
}
AddAtEnd(struct me **q, int y)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
p = malloc(sizeof(struct me));
p->data = y;
p->prev = NULL;
p->next = NULL;
*q = p;
}
else
{
while(p->next != NULL)
{
p = p->next;
}
w = malloc(sizeof(struct me));
w->data = y;
w->prev = p;
w->next = p->next;
p->next = w;
}
return;
}
DeleteAtBeg(struct me **q)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
err_msg(1);
}
else
{
if(p->next == NULL)
{
err_msg(2);
*q = p->prev;
free(p);
}
else
{
w = p->next;
*q = w;
(*q)->prev = p->prev;
free(w->prev);
}
}
return;
}
DeleteAtPos(struct me *q,int x)
{
struct me *p,*w, *z;
int i;
p = q;
w = q;
if(p == NULL)
{
err_msg(6);
}
else
{
for(i = 0; i < x; i++)
{
w = w->next;
if(w == NULL)
{
printf("\tCANNOT DELETE THERE ARE LESS THAN");
printf("\n\t%d ELEMENTS IN THE LIST", x);
return;
}
}
err_msg(2);
z = w->next;
z->prev = NULL;
z->next->prev = w;
w->next = z->next;
free(z);
return;
}
}
DeleteAtEnd(struct me **q)
{
struct me *p,*z;
p = *q;
if(p == NULL)
{
err_msg(1);
}
else
if(p->next == NULL)
{
*q = p->prev;
free(p);
}
else
{
while(p->next->next != NULL)
{
p = p->next;
}
z = p->next;
p->next = z->next;
z->next = NULL;
z->prev = NULL;
free(z);
}
return;
}
UsingSelectionSort(struct me **q)
{
int c = 0,x,y;
struct me *p, *w, *z, *v, *o;
p = *q;
v = *q;
while( p != NULL)
{
c++;
p = p->next;
}
printf("\n\tNUMBER OF NODES IN LINKED LIST IS : %d\n",c);
if(v == NULL)
{
err_msg(1);
}
else if(v->next == NULL)
{
err_msg(4);
}
else
{
for(w = *q ; w != NULL; w = w->next)
{
x=9999;
for(z = w ; z != NULL; z = z->next)
{
if(z->data < x)
{
x = z->data;
o = z;
}
}
o->data = w->data;
w->data = x;
}
}
return;
}
DisplayN(struct me *q)
{
struct me *z;
z = q;
if(z==NULL)
{
err_msg(1);
}
while(z->next != NULL)
{
printf("\t%d", z->data);
z = z->next;
printf("\n");
}
printf("\t%d", z->data);
return;
}
DisplayR(struct me *q)
{
struct me *z,*w;
if(q == NULL)
{
err_msg(1);
}
else
{
for(z = q; z->next != NULL ; z = z->next)
{
}
for(w = z; w->prev != NULL ; w = w->prev)
{
printf("\t%d", w->data);
printf("\n");
}
printf("\t%d", w->data);
}
return;
}
err_msg(int p)
{
if(p==1)
printf("\tTHE LIST IS EMPTY");
if(p==2)
printf("\tHELLO");
if(p==3)
printf("\tWRONG CHOICE");
if(p==4)
printf("\n\tTHE LIST IS ALREADY SORTED");
if(p==5)
printf("\n\tINSERTION AT POS REQUIRED ONE NODE");
if(p==6)
printf("\n\tDELETION AT POS REQUIRED TWO NODE");
}
C LANGUAGE BOOK |
No comments:
Post a Comment