• USA : +1 973 910 5725
  • INDIA: +91 905 291 3388
  • info@tekslate.com
  • Login

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

 

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 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();

}

“At TekSlate, we are trying to create high quality tutorials and articles, if you think any information is incorrect or want to add anything to the article, please feel free to get in touch with us at info@tekslate.com, we will update the article in 24 hours.”

0 Responses on Doubly Linked List in Data Structures"

Leave a Message

Your email address will not be published. Required fields are marked *

Site Disclaimer, Copyright © 2016 - All Rights Reserved.