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