Doubly Linked List in Data Structures

21 September, 2018

Related Blogs

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 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.     41  

Insertion Operation

  • Insertion of first Node
ptr 7 bl=cur; cur 7 fl =ptr; rur=cur; 42    
  1.  Insertion after a given node:

cur 7 fl =ptr àfl; cur 7 bl =ptr; ptr 7 fl 7 bl=cur; ptr 7fl =cur; 40  

Deletion Operation

  1. Deleting First Node

ptr 7fl 7bl= ptr 7bl; root =ptr 7fl;   43  
  1. Deleting a specified node:

ptr 7 fl 7bl = ptr 7bl; ptr 7 bl 7fl= ptr 7fl;   43  


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 7”,ptr7data); if(ptr7flNULL); last=ptr; ptr=ptr-fl; } printf(“\n reverse list”); ptr=last; while(ptr!=Null) { printf(“%d 7”,ptr 7 data);               ptr=ptr7 bl; } } void insertion() { int ele; char ch; ptr=root; cur=(node *) malloc*(sizeof(nodes)); printf(“enter data for node” ); scanf(“%d”, &cur 7 data); cur 7 fl=cur 7 bl=NULL; ffush(stdin); printf(“do you want to insert first(Y/N):”); scanf(“%c”,&ch); if(ch==’Y’ || ch==’Y’) { ptr7 bl=cur; cur7  fl=ptr; root=cur; } Else         { printf(“After which element you want to insert:”); scanf(“%d”,&ele); while(ptr!=NULL) { if(ptr7 data== ele) { cur 7 fl=ptr 7 fl; cur 7 bl=ptr; ptr7 fl 7 bl=cur; ptr7 fl=cur; break; } else ptr=ptr7 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’) { ptr7 fl 7bl=ptr 7 bl; root=ptr 7 fl; } else { printf(“which element you want to delete :”); scanf(“%d”, &ele); while(ptr!=NULL) { if(ptr 7 data==ele) { ptr7 fl 7 bl=ptr -7bl; ptr 7 bl 7 fl=ptr7fl; }                 else ptr=ptr7 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; cur7 fl=cur 7 bl=NULL; if(root==NULL) root=cur; else             { cur7 bl=ptr; ptr7 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(); }
About Author


Author Bio

TekSlate is the best online training provider in delivering world-class IT skills to individuals and corporates from all parts of the globe. We are proven experts in accumulating every need of an IT skills upgrade aspirant and have delivered excellent services. We aim to bring you all the essentials to learn and master new technologies in the market with our articles, blogs, and videos. Build your career success with us, enhancing most in-demand skills .