Doubly Linked List in Data Structures

Doubly Linked List

In a single linked list, it is possible to move only in the direction of links, that is we have been restricted to traversing linked list in only one direction. In the linked lists, each node provides information about where is the next node in the list. It has no knowledge about where the previous node lies in memory. If we are at say the 15th node in the list, then to reach the 14^th node we have to traverse the list right from the first node. To avoid this we can store in each node not only the address of next node but also. The address of the previous node in the linked list this arrangement is often known as ‘Doubly linked list’ in data structures. The list can be traverse in either a forward or backward direction. Each node in doubly linked list must contain two link fields instead of one. Here a node has at least three fields say data, left link and right link.      

Insertion Operation

• Insertion of first Node

ptr  bl=cur; cur  fl =ptr; rur=cur;    

1.  Insertion after a given node:

cur  fl =ptr àfl; cur  bl =ptr; ptr  fl  bl=cur; ptr fl =cur;  

Deletion Operation

1. Deleting First Node

ptr fl bl= ptr bl; root =ptr fl;    

1. Deleting a specified node:

ptr  fl bl = ptr bl; ptr  bl fl= ptr fl;    

Program

Implementation of Doubly linked list #include <stdio.h> #include<conio.h> # include<stdlib.h> struct dlist { int data; struct dlist ,*fl,*bl; }; typedef struct dlist node; node *ptr,*root,*cur,*last; void display() { ptr=root; last=NULL; printf(“The list is \n”); while(ptr!=NULL) { printf(“%d ”,ptrdata); if(ptrflNULL); last=ptr; ptr=ptr-fl; } printf(“\n reverse list”); ptr=last; while(ptr!=Null) { printf(“%d ”,ptr  data);               ptr=ptr bl; } } void insertion() { int ele; char ch; ptr=root; cur=(node *) malloc*(sizeof(nodes)); printf(“enter data for node” ); scanf(“%d”, &cur  data); cur  fl=cur  bl=NULL; ffush(stdin); printf(“do you want to insert first(Y/N):”); scanf(“%c”,&ch); if(ch==’Y’ || ch==’Y’) { ptr bl=cur; cur  fl=ptr; root=cur; } Else         { printf(“After which element you want to insert:”); scanf(“%d”,&ele); while(ptr!=NULL) { if(ptr data== ele) { cur  fl=ptr  fl; cur  bl=ptr; ptr fl  bl=cur; ptr fl=cur; break; } else ptr=ptr fl; } void deletion() { int ele; char ch; ptr=root;           fflush(stdin); printf(“Do you want to delete first(y/n)”); scanf(“%c”, &ch); if(ch==’ Y’||ch=’ Y’) { ptr fl bl=ptr  bl; root=ptr  fl; } else { printf(“which element you want to delete :”); scanf(“%d”, &ele); while(ptr!=NULL) { if(ptr  data==ele) { ptr fl  bl=ptr -bl; ptr  bl  fl=ptrfl; }                 else ptr=ptr fl; } } } void main() { int a,n; root=NULL; printf(“Enter data for node(-1)”); scanf(“%d”,&a); while(a!=-1) { cur=(node*) malloc(sizeof(nodes)); cur-> data =a; cur fl=cur  bl=NULL; if(root==NULL) root=cur; else             { cur bl=ptr; ptr fl=cur; } ptr=cur; printf(“enter data for node(-1)”); scanf(“%d”,&a); } printf(“1.display\n”); printf(“2.Insertion\n”); printf(“3. deletion \n”); printf(“4. Exit \n”); do { printf(“Enter four option :”); scanf(“%d”,&n); switch(n) { case 1: display();break; case 2: insertion();break; case 3: deletion(); break; case 4: exit(0); break; } } while(n<=4); getch(); }