Doubly Linked List
Doubly linked list is a linear data structure which is type of linked list in which each node consist of data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.The two links help us to traverse the list in both backward and forward direction. But storing an extra link requires some extra space.
Singly linked list  Doubly linked list 

A singly linked list is a linked list where the node contains some data and a pointer to the next node in the list  A doubly linked list is complex type of linked list where the node contains some data and a pointer to the next as well as the previous node in the list 
It allows traversal only in one way  It allows a two way traversal 
It uses less memory per node (single pointer)  It uses more memory per node(two pointers) 
Complexity of insertion and deletion at a known position is O(n)  Complexity of insertion and deletion at a known position is O(1) 
If we need to save memory and searching is not required, we use singly linked list  If we need better performance while searching and memory is not a limitation, we go for doubly linked list 
If we know that an element is located towards the end section, eg. ‘zebra’ still we need to begin from start and traverse the whole list  If we know that an element is located towards the end section e.g. ’zebra’ we can start searching from the Back. 
Singly linked list can mostly be used for stacks  They can be used to implement stacks, heaps, binary trees. 
Advantages of Doubly Linked list
 We can traverse in both directions i.e. from starting to end and as well as from end to starting.
 It is easy to reverse the linked list.
 If we are at a node, then we can go to any node. But in linear linked list, it is not possible to reach the previous node.
Disadvantages of Doubly Linked list
 It requires more space per space per node because one extra field is required for pointer to previous node.
 Insertion and deletion take more time than linear linked list because more pointer operations are required than linear linked list.
Applications
 The browser cache which allows you to hit the BACK buttons (a linked list of URLs).
 Applications that have a Most Recently Used (MRU) list (a linked list of file names).
 A stack, hash table, and binary tree can be implemented using a doubly linked list.
 Undo functionality in Photoshop or Word (a linked list of state).
 A great way to represent a deck of cards in a game.
Node Creation
struct node { struct node *prev; int data; struct node *next; }; struct node *head; 

Insertion at Beginning in Doubly LinkedList
Algorithm
 IF ptr = NULL
 SET NEW_NODE = ptr
 SET ptr = ptr > NEXT
 SET NEW_NODE > DATA = VAL
 SET NEW_NODE > PREV = NULL
 SET NEW_NODE > NEXT = START
 SET head > PREV = NEW_NODE
 SET head = NEW_NODE
 EXIT


Program Code
#include<stdio.h> #include<stdlib.h> #include<conio.h> void insertbeginning(int); struct node { int data; struct node *next; struct node *prev; }; struct node *head; void main () { clrscr(); int choice,item; do { printf("\nEnter the item which you want to insert: "); scanf("%d",&item); insertbeginning(item); printf("Press 0 to insert more! "); scanf("%d",&choice); }while(choice == 0); } void insertbeginning(int item) { struct node *ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { if(head==NULL) { ptr>next = NULL; ptr>prev=NULL; ptr>data=item; head=ptr; } else { ptr>data=item; ptr>prev=NULL; ptr>next = head; head>prev=ptr; head=ptr; } } } 

Output
For more Data Structures & Algorithms Tutorials Click here