Doubly Linked list

A doubly linked list contains an extra pointer which points to the previous element of a list and which does not exist in a singly linked list.This makes easy traversal of a linked list to the previous elements.

Algorithm for insertion 

of an element in a Doubly Linked List . Insertion can be classified into 3 different methods.

1. Insertion at the Head
2. Insertion at a given postion 
3. Insertion at the end of the Linked List 

Insertion at the head

1.Allocate a node 2. Put in the data 3.Make the next of the new node as head and previous as Null 4.Change the prev of head node to new Node. 5. Move prev of head to point to the new node

Insertion after a given position

1.Allocate a new Node 2.Put in the data 3.Make next of new node as next of prev node new_node->next=prev-node->next 4.Make the next of prev_node as new_node prev-node->next=new_node 5.Make prev-node as previous of new-node new_node->prev= prev_node 6.Change previous of new_node's next node

Insertion of a node towards the end

1.Allocate a node 2.Put in the data 3.This new node is going to be the last node, so make next of it as NULL new_node->next=NULL 4.Traverse the list to the end 5.Change the next of last node as new node 6.Make the last node as prev of new node

Algorithm for deletion of a node

1.If node to be deleted is the head node head=del_node->next 2.Check the next node only if the node to be deleted is not the last node. if(del->next != NULL) del->next->prev = del->prev; 3.Check the prev node only if the node to be deleted is not the first node. if(del->prev != NULL) del->prev->next = del->next; 4.Delete the memory

Algorithm for reversing a Doubly Linked List

/* Function to reverse a Doubly Linked List */ void reverse(struct node **head_ref) { struct node *temp = NULL; struct node *current = *head_ref; /* swap next and prev for all nodes of doubly linked list */ while (current != NULL) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } /* Before changing head, check for the cases like empty list and list with only one node */ if(temp != NULL ) *head_ref = temp->prev; }
Source: GeeksforGeeks

Advantages over Singly Linked list

1. Can be traversed front and back from any location
2. Less ambiguity in deleting an element from the linked list.

Disadvantages over a Singly Linked list

1. Every Node takes in an extra pointer when a linked list could be created with a single pointer.
2. Extra maintenance.

Important Links to Follow
Doubly Linked List(Geeksforgeeks)
Code for doubly Linked List