Double Linked List

Double Linked List

            A Double Linked List is represented as follows

The main disadvantages of single linked list is that traversal is possible only in one direction i.e., forward direction.  If we are pointing to a node, say ‘P’, then we can move only in one direction of link.  Suppose, if we want to find the predecessor of ‘P’, then we have to start from the beginning of the linked list.  Thus given the address of a node, we can only find the address of successor, and it is not possible to find the address of predecessor directly.  To overcome this we use double Linked List.

            In order to facilitate  faster processing of data, it is require to traverse the list in both direction.  Such a list is called Double Linked List.  Here each node contain 3-fields, two of which are link fields and one is data field.  Thus a typically node is as follows:

  

LLink

Data

RLink

            

      RLink, links in the forward direction and LLink, links in backward direction i.e., RLink contains the address of successor node and LLink contains address of predecessor node.  Double Linked List is also called as Two Way Chain.  Address of the leftmost node is L and address of rightmost node R.  if we traverse in forward direction R is the last node.  Hence Rà RLink=Null.  Similarly, if it traverse in backward direction L is the last node.  Hence  LàLLink=Null.

            Suppose, if X is the address of a node then XàLLink represent the address of the predecessor and Xà RLink represent the address of successor.  Declaration of Double Linked List  in C is as follows:

struct node

{

   Struct node *LLink;

   int data;

   struct node *RLink;

};