Doubly Linked List

Definition
Memory representation
operations

1. Doubly Linked List Mrs.G.Chandraprabha,M.Sc.,M.Phil ., Assistant Professor, Department of Information Technology, V.V.Vanniaperumal College for Women, Virudhunagar .

2. Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list. Link  − Each link of a linked list can store a data called an element. Next  − Each link of a linked list contains a link to the next link called Next. Prev  − Each link of a linked list contains a link to the previous link called Prev. Linked List  − A Linked List contains the connection link to the first link called First and to the last link called Last. Doubl y Lin k ed Li s t

3. Memory Representation of a doubly linked list is shown in the following image. Generally, doubly linked list consumes more space for every node and therefore, causes more expansive basic operations such as insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the directions (forward and backward). In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer points to the starting address 1. Since this is the first element being added to the list therefore the  prev  of the list  contains  null. The next node of the list resides at address 4 therefore the first node contains 4 in its next pointer. We can traverse the list in this way until we find any node containing null or -1 in its next part. Memory Representation of a doubly linked list

4. N O DE A B C A doubly linked list contain three fields: an integer value, the link to the next node, and the link to the previous node . P revious D ata next NULL 11 786 7 86 2 00 400 200 656 400 786 777 NULL Doubly Linked List Representation

5. Doubly Linked List contains a link element called first and last. Each link carries a data field(s) and two link fields called next and prev. Each link is linked with its next link using its next link. Each link is linked with its previous link using its previous link. The last link carries a link as null to mark the end of the list. Doubly Linked List Representation

6. Insertion  − Adds an element at the beginning of the list. Deletion  − Deletes an element at the beginning of the list. Insert Last  − Adds an element at the end of the list. Delete Last  − Deletes an element from the end of the list. Insert After  − Adds an element after an item of the list. Delete  − Deletes an element from the list using the key. Display forward  − Displays the complete list in a forward manner. Display backward  − Displays the complete list in a backward manner. Basic Operations ON Doubly Linked List

7. Structure of DLL //holds the address of previous node struct node { int data; node*next; n o de*p r ev ious; }; . D ata . next p r ev iou s . inf

8. As in doubly linked list, each node of the list contain double pointers therefore we have to maintain more number of pointers in doubly linked list as compare to singly linked list. There are two scenarios of inserting any element into doubly linked list. Either the list is empty or it contains at least one element. Perform the following steps to insert a node in doubly linked list at beginning. Allocate the space for the new node in the memory. This will be done by using the following statement. ptr  = ( struct  node *) malloc ( sizeof ( struct  node));   Check whether the list is empty or not. The list is empty if the condition head == NULL holds Insertion in doubly linked list at beginning

9. In that case, the node will be inserted as the only node of the list and therefore the prev and the next pointer of the node will point to NULL and the head pointer will point to this node. ptr ->next = NULL;            ptr -> prev =NULL;            ptr ->data=item;           head= ptr ;   In the second scenario, the condition  head == NULL  become false and the node will be inserted in beginning. The next pointer of the node will point to the existing head pointer of the node. The prev pointer of the existing head will point to the new node being inserted. Insertion in doubly linked list at beginning

10. This will be done by using the following statements. ptr ->next = head;      head→prev = ptr ;   Since, the node being inserted is the first node of the list and therefore it must contain NULL in its prev pointer. Hence assign null to its previous part and make the head point to this node. ptr→prev  =NULL   head =  ptr    Insertion in doubly linked list at beginning

11. Insertion in doubly linked list at beginning

12. Add a node after a given node.: We are given pointer to a node as prev_node , and the new node is inserted after the given node. Insertion in doubly linked list after given Node

13. The new node is always added after the last node of the given Linked List. Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node. Insertion in doubly linked list At end

14. Deletion in a doubly linked list can happen at various places in the list. At the beginning of the doubly linked list. At the end of the doubly linked list. At a given position in the doubly linked list. Deletion in doubly linked list

15. Copy the head node in some temporary node. Make the second node as the head node. The  prev  pointer of the head node is referenced to NULL. Delete the temporary node. Deletion at the beginning of the doubly linked list

16. Suppose you want to delete the second node from the list. Start traversing the linked list from the head until the position = 2 of the node to be deleted. Let the node at the position 2 of the list be  temp . Assign the  next  pointer of temp to temp's previous node's  next  pointer. Assign the temp's  prev  pointer to temp's next node's  prev  pointer. Delete the  temp  node. Deletion  at the given position in the doubly linked list

17. Deletion  at the given position in the doubly linked list

18. Deletion  at the end of the doubly linked list Copy the  last  node to a temporary node. Shift the  last  node to the second last position. Make the  last  node's  next  pointer as NULL. Delete the temporary node.

19. THANK YOU