Tuesday, September 29, 2015

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



Insertion after a given position


Insertion of a node towards the end



Algorithm for deletion of a node



Algorithm for reversing a Doubly Linked List


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