Data Structure (2130702)

Need of Doubly Linked List

• In certain Applications, it is very desirable that a list be traversed in either forward or reverse direction.
• This property implies that each node mist contain two link fields instead of usual one.
• The links are used to denote Predecessor and Successor of node.
• The link denoting its predecessor is called Left Link.
• The link denoting its successor is called Right Link.
• A list containing this type of node is called doubly linked list or two way chain.

Procedure: DOU_INS (L,R,M,X)

• This algorithm inserts a new node in doubly linked linear list.
• The insertion is to be performed to the left of a specific node with its address given by the pointer variable M.
• Typical node of doubly linked list contains following fields LPTR, RPTR and INFO.
• LPTR is pointer variable pointing to Predecessor of a node.
• RPTR is pointer variable pointing to Successor of a node.
• L & R are pointer variables pointing for Leftmost and Rightmost node of Linked List.
• NEW is the address of New Node.
• X is value to be inserted.

1. [Create New Empty Node]
   NEW<--NODE
   
2. [Copy information field]
   INFO(NEW)<--X
   
3. [Insert into an empty list]
   IF R=NULL
   THEN LPTR(NEW)<--RPTR(NULL)<--NULL
      L<--R<--NEW
      Return
   
4. [Is left most insertion ?]
   IF M=L
   THEN LPTR(NEW)<--NULL
      RPTR(NEW)<--M
      LPTR(M)<--NEW
      L<--NEW
      Return
   
5. [Insert in middle]
   LPTR(NEW)<--LPTR(M)
   RPTR(NEW)<--M
   LPTR(M)<--NEW
   RPTR(LPTR(NEW))<--NEW
   Return