Double Link List..
a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator
Advantage
A doubly linked list can be traversed in both directions (forward and backward). A singly linked list can only be traversed in one direction.
A node on a doubly linked list may be deleted with little trouble, since we have pointers to the previous and next nodes. A node on a singly linked list cannot be removed unless we have the pointer to its predecessor.
a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator
Advantage
A doubly linked list can be traversed in both directions (forward and backward). A singly linked list can only be traversed in one direction.
A node on a doubly linked list may be deleted with little trouble, since we have pointers to the previous and next nodes. A node on a singly linked list cannot be removed unless we have the pointer to its predecessor.
On the flip side however, a doubly linked list needs more operations while inserting or deleting and it needs more space (to store the extra pointer).
Implementation: Complete menu base code
#include<stdio.h>
#include<conio.h>
/* Double Link List Example
Developed By Girfa
do not use it on any other website
*/
typedef struct st_dlist
{
struct st_list *pre;
int data;]
struct st_list *next;
}dnode;
/* Function Prototype */
dnode * create(int);
void addbegin(int,dnode**,dnode**);
void addlast(int,dnode**,dnode**);
void addbefore(int,int,dnode**,dnode**);
void addafter(int,int,dnode**,dnode**);
void del(int,dnode**,dnode**);
void print(dnode*);
void main()
{
dnode *head=NULL,*tail=NULL;
int n,s,opt;
/* Double Link List Example
Developed By Girfa
do not use it on any other website
*/
typedef struct st_dlist
{
struct st_list *pre;
int data;]
struct st_list *next;
}dnode;
/* Function Prototype */
dnode * create(int);
void addbegin(int,dnode**,dnode**);
void addlast(int,dnode**,dnode**);
void addbefore(int,int,dnode**,dnode**);
void addafter(int,int,dnode**,dnode**);
void del(int,dnode**,dnode**);
void print(dnode*);
void main()
{
dnode *head=NULL,*tail=NULL;
int n,s,opt;
do
{
clrscr();
printf("\n1. Print\n2. Add Begin\n3. Add Last\n4. Add Before to given number\n5. Add after to given number\n6. Delete\n0. Exit \nEnter your choice>> ");
fflush(stdin);
scanf("%d",&opt);
switch(opt)
{
case 1:
print(head);
getch();
break;
case 2:
printf("Enter Number for add begin>> ");
scanf("%d",&n);
addbegin(n,&head,&tail);
break;
case 3:
printf("Enter Number for add Last>> ");
scanf("%d",&n);
addlast(n,&head,&tail);
break;
case 4:
printf("Enter number for search>> ");
scanf("%d",&s);
printf("enter number for Add in List>> ");
scanf("%d",&n);
addbefore(s,n,&head,&tail);
break;
case 5:
printf("Enter number for search>> ");
scanf("%d",&s);
printf("enter number for Add in List>> ");
scanf("%d",&n);
addafter(s,n,&head,&tail);
break;
case 6:
printf("Enter number for delete>> ");
scanf("%d",&n);
del(n,&head,&tail);
break;
case 0:
break;
default:
printf("\nInvalid Choice ");
}
}while(opt!=0);
}
dnode* create(int n)
{
dnode *nw;
nw=(dnode*) malloc(sizeof(dnode));
nw->data=n;
nw->next=NULL;
nw->pre=NULL;
return(nw);
}
void addbegin(int n,dnode **hd,dnode **tl)
{
dnode *nw=create(n);
if(*hd==NULL)
{
*hd=nw;
*tl=nw;
}
else
{
(*hd)->pre=nw;
nw->next=*hd;
*hd=nw;
}
}
void print(dnode *st)
{
dnode *pt;
for(pt=st;pt!=NULL;pt=pt->next)
printf("[ %d ]",pt->data);
}
void addlast(int n,dnode **hd,dnode **tl)
{
dnode *nw=create(n);
if(*hd==NULL)
{
*hd=nw;
*tl=nw;
}
else
{
(*tl)->next=nw;
nw->pre=*tl;
*tl=nw;
}
}
void addbefore(int s,int n,dnode **hd,dnode **tl)
{
dnode *nw,*pt;
for(pt=*hd;pt!=NULL;pt=pt->next)
{
if(pt->data==s)
{
break;
}
}
if(pt==NULL)
{
printf("\nSearch Value not found");
getch();
}
else
{
nw=create(n);
if(pt==*hd)
{
(*hd)->pre=nw;
nw->next=*hd;
*hd=nw;
}
else
{
nw->next=pt;
nw->pre=pt->pre;
(pt->pre)->next=nw;
pt->pre=nw;
}
}
}
void addafter(int s,int n,dnode **hd,dnode **tl)
{
dnode *nw,*pt;
for(pt=*hd;pt!=NULL;pt=pt->next)
{
if(pt->data==s)
{
break;
}
}
if(pt==NULL)
{
printf("\nSearch Value not found");
getch();
}
else
{
nw=create(n);
if(pt==*tl)
{
nw->pre=*tl;
(*tl)->next=nw;
*tl=nw;
}
else
{
nw->pre=pt;
nw->next=pt->next;
(pt->next)->pre=nw;
pt->next=nw;
}
}
}
void del(int n,dnode **hd,dnode **tl)
{
dnode *pt;
for(pt=*hd;pt!=NULL;pt=pt->next)
{
if(pt->data==n)
{
break;
}
}
if(pt==NULL)
{
printf("Search value not found");
getch();
}
else
{
if(pt==*hd)
{
*hd=pt->next;
(*hd)->pre=NULL;
free(pt);
}
else
{
if(pt==*tl)
{
*tl=pt->pre;
(*tl)->next=NULL;
free(pt);
}
}
}
}
No comments:
Post a Comment