Monday, June 4, 2012

C program on doubly linked list and its traversal


In linear linked list one can not traverse such list from rear end. When this facility is required, the appropriate data structure is doubly linked list. Each node of such a list contains two address pointers, one points to it's previous node and another points to the next node.

Here is a program that will create a doubly linked list and the list will be traversed from both sides.

# include < stdio.h >
# include < stdlib.h >
struct list
{
char info[20];
struct list *next;
struct list *prev;
};
struct list *new1,*node;
void create(struct list *s,struct list *e)
{
char ch;
node=s;
printf("\nWant to create a node(y/n):");
ch=getche();
while (ch != 'n')
{
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
printf("\n Enter the string value:- ");
gets(node->info);
node->next = e;
e->prev=node;
printf("\n Enter choice--'n' for break: ");
ch = getche();
}
}
void displayL (struct list *s,struct list *e)
{
node = s->next;
while (node!=e)
{
printf("\n 0x%x--%s", node,node->info);
node = node->next;
}
}
void displayR (struct list *e,struct list *s)
{
node = e->prev;
while (node!=s)
{
printf("\n 0x%x--%s", node,node->info);
node = node->prev;
}
}

void main()
{
struct list *start,*end;
clrscr();
start=(struct list *) malloc(sizeof(struct list));;
end=(struct list *) malloc(sizeof(struct list));;
create(start,end);
printf("\n Created list is as follows(L ->R)\n");
displayL(start,end);
printf("\n Created list displayed from R->L\n");
displayR(end,start);

getch();
}

How this doubly linked list program works – a complete study

 First of all each node of this doubly linked list contains three compartments. Two internal or address pointers and one information part. One address pointer points the next node and the other points the previous node of the doubly linked list.

In ‘void main ()’ function, two list pointers are created without any value in information part variables. One list pointer points the first node of the doubly linked list while the other points the last node.

‘void create (struct link*, struct link*)’ function of this doubly linked list program is used to create the dynamic list. Both the list pointers of the doubly linked list are passed as argument to this function. In side the function nodes are created and the new node is connected to the doubly linked list in proper way.

‘void displayL (struct link*, struct link*)’ and ‘void displayR (struct link*, struct link*)’ functions are used in this program to display the doubly linked list from left to right and right to left direction respectively.

No comments:

Post a Comment

Subscribe via email

Enter your email address:

Delivered by FeedBurner