Introduction to Doubly Linked List

In this type of liked list each node holds two-pointer field. Pointers exist between adjacent nodes in both directions.The list can be traversed either forward or backward

The doubly linked list is a linked list made up of nodes that have two pointers. These pointers point to the next and previous node.

In contrast to the singly linked list, our doubly linked list node will have two pointers LITERALLY pointing to the next and previous node.

For all linked list implementations, we must have either a head and/or a tail. I will mention this just in case. The head and tail node are the first and last node of a linked list respectively.

So our Node container (in whatever language you program in), will have the following attributes.

Data.
Next node.
Previous node.

Advantages

1.Doubly Linked List are more convenient than Singly Linked List since we maintain links for bi-directional traversing
2.We can traverse in both directions and display the contents in the whole List.
3.In Doubly Linked List we can traverse from Head to Tail as well as Tail to Head.
4. Each Node contains two fields, called Links , that are references to the previous and to the Next Node in the sequence of Nodes.
5. The previous link of the first node and the next link of the last node points to NULL.

 

[code language=”cpp”]

#include<stdio.h>

#include<malloc.h>

#include<conio.h>

typedef struct Node

{

struct Node *prev;

int info ;

struct Node *next;

}node;

void createdub(node**,node**);

void display(node *);

void main()

{

int ch;

node *start ,*end ;

start = end = NULL;

clrscr();

createdub(&start,&end);

printf("\nThe list is : ");

display(start);

getch();

}

void createdub(node **start,node **end)

{

int i,item ,k=1;

printf("\nEnter number of node: ");

scanf("%d",&i);

while(i)

{ node *ptr;

printf("\nEnter the info for node %d : ",k);

scanf("%d",&item);

ptr=(node*)malloc(sizeof(node));

ptr->info=item;

if(*start==NULL)

{

ptr->prev = ptr->next = NULL ;

*start = *end = ptr ;

}

else

{

ptr->prev = *end;

(*end)->next = ptr ;

ptr->next= NULL;

(*end)=ptr;

}

i–;

k++;

}

}

void display(node *start)

{

while(start !=NULL)

{

printf("\t %d",start->info);

start = start->next;

}

}

[/code]