  # Doubly Linked List in Data Structures

Blog Author

Tekslate

Published Date

21st September, 2018

Ratings

Views

927

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 14th 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 ”,ptr data); if(ptr flNULL); 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=ptr fl; }                 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(); } 