Doubly linked list

Doubly linked linear list

1. Doubly Linked Linear List P.M.Patil

2. As compare to singly linked list we can easily traverse the DLL in for word as well as back word direction. Each node of the DLL has three parts. It’s node has two pointers to store next node address and previous node address of the list. Doubly Linked Linear List

3. Doubly Linked Linear List Lptr : this pointer will store address of predecessor node (previous) Rptr : this pointer will store address of successor node(next) Info : will store information of that node Data / Node info rptr / l ptr

4. Head Node / 10 20 30 / Doubly Linked Linear List / Neeta Veena Shilpa / / 10.25 34.9 16 / Head Node Head Node

5. Doubly Linked Linear List Operations Insert First Insert Last Delete First Delete Last Display list in forward direction Display list in backward direction Search Insert n Delete n

6. InsertFirst operation Doubly Linked Linear List Head Node / 10 20 30 / 50 New Node 1. 2. 3. 4. lptr r ptr r ptr lptr

7. InsertFirst operation Doubly Linked Linear List Head Node / 10 20 30 / 50 New Node lptr r ptr

8. Insert First Algorithm Procedure INSERTFIRST () This procedure will insert a new node at first position in linked list. Each node of the list has three parts info, lptr and rptr . Head is a headnode of the list. New is a newnode . [create a new node] allocate(new) Read(info(New)) lptr (New)<-NULL rptr (New)<- NULL 2. [attach new node] lptr (New) <- Head rptr (New) <- rptr (Head) // adress of 10 rptr (Head) <- New lptr ( rptr (Head)) <- New Write(‘New node is attached’) 3. [finished] Exit

9. InsertLast operation Doubly Linked Linear List Head Node / 10 20 30 / 50 New Node lptr r ptr Temp

10. Insert Last Algorithm Procedure INSERTLAST () This procedure will insert a new node at the end of the linked list. Each node of the list has three parts info, lptr and rptr . Head is a headnode of the list. New is a newnode . [create a new node] allocate(new) Read(info(New)) lptr (New)<-NULL rptr (New)<- NULL [set temp to the last node] Temp<- Head while ( rptr (Temp) # NULL) Temp<- rptr (Temp) 3 . [attach new node at the end of list] rptr (Temp) <- New lptr (New) <- temp; Write(‘New node is attached’) 4 . [finished] Exit

11. Display Algorithm:Forword direction Procedure Display () This procedure will display all elements of the linked list in forword direction. Each node of the list has three parts info, lptr and rptr . Head is a headnode of the list. Temp is temporary pointer variable which points to any node of the list. [Check list is empty or not] if ( rptr (Head) = NULL) write(‘linked list is empty’) Exit Endif [display the list] Temp<- Head while ( rptr (Temp) # NULL) Temp<- rptr (Temp) Write( info(Temp) ) 3. [finished] Exit

12. Display Algorithm: Backword direction Procedure Display () This procedure will display all elements of the linked list in backword direction. Each node of the list has three parts info, lptr and rptr . Head is a headnode of the list. Temp is temporary pointer variable which points to any node of the list. [Check list is empty or not] if ( rptr (Head) = NULL) write(‘linked list is empty’) Exit Endif [set temp to last node] Temp <- Head while ( rptr (Temp) # NULL) Temp<- rptr (Temp) [display the list] while ( lptr (Temp) # NULL) write( info(Temp) ) Temp<- lptr (Temp) 3. [finished] Exit

13. DeleteFirst operation Doubly Linked Linear List Head Node Temp / 10 20 30 / lptr r ptr

14. Delete First Algorithm Procedure DELETEFIRST () This procedure will delete a first node from the linked list. Each node of the list has three parts info, lptr and rptr . Head is a headnode of the list. Temp is a temporary pointer variable which points to any node of the list. [set Temp to First node] Temp <- link(Head) (‘temp is set to 10’) 2. [delete first node] rptr (Head) <- rptr (Temp) (‘address of 20’) lptr ( rptr (Temp)) <- Head Write(‘first node is deleted’) Free(Temp) 3. [finished] Exit

15. Head Node / 10 20 30 / Temp Delete Last Algorithm

16. Delete Last Algorithm Procedure DELETELAST () This procedure will delete a LAST node from the linked list. Each node of the list has three parts info, lptr and rptr . Head is a headnode of the list. Temp is a temporary pointer variable which points to any node of the list. [set Temp to headnode ] Temp <- Head 2. [move temp to second last node of the list] while( rptr ( rptr (Temp)) # NULL) Temp <- rptr (Temp) 3. [delete last node] X <- rptr (Temp) rptr (Temp) <- NULL Write(‘Last node is deleted’) Free(X) 3. [finished] Exit