Show Get this book -> Problems on Array: For Interviews and Competitive Programming In this article, we have explored Circular Doubly Linked List and operations that can be performed on it. It is a combination to two Data Structures namely Circular Linked List and Doubly Linked List. Table of contents: Pre-requisites: Circular Doubly Linked List is a linear data structure which consists of nodes. Each node is divided into three parts containing data part,pointer to previous node and pointer to next node. Unlike Linked List or Doubly Linked List, Circular Doubly Linked List doesn't contain NULL values in any of the nodes rather the head's previous pointer points to last node and last node's next pointer points to head. This is an advantage as NULL is considered as a special case. Node structure: class ListNode: def __init__(self,value): self.prev=None self.data=value self.next=NoneVarious operations can be performed on Circular Doubly Linked List as discussed below. Insertion at the beginningIn this operation a new node is inserted at the beginning of CDLL. The basic idea is to update the head node of Circular Doubly Linked List which is the starting point and the rest of the process remain the same as in inserting in any other position. Note: As any node in Circular Doubly Linked List can act as the head node, it is important to maintain it but it does not create issues if access to head node is lost provided we have access to any node of the Circular Doubly Linked List. Let's understand through an illustration. Given CDLL Create a new node with value 2 Take a variable ptr and let it point to head initially Traverse through the list to make ptr point to the last node Change the pointers as follows ptr->next=newnode head=newnode -The modified list ALGORITHM
CODE SNIPPETdef insertAtBeginning(value): global head newnode=ListNode(value) if head is None: head=newnode return ptr=head while ptr.next is not head: ptr=ptr.next ptr.next=newnode newnode.prev=ptr newnode.next=head head.prev=newnodeInsertion at the endIn this operation a new node is inserted at the end of CDLL. Similar to the previous case, the head is modified in this case as well as the last node points to the head node through the next pointer. Let's understand through an illustration. Given CDLL Create a new node with value 2 Take a variable ptr and let it point to head initially Traverse through the list to make ptr point to the last node Change the pointers as follows newnode->next=head The modified list. ALGORITHM
CODE SNIPPETdef insertAtEnd(value): global head newnode=ListNode(value) if head is None: head=newnode return ptr=head while ptr.next is not head: ptr=ptr.next newnode.next=head ptr.next=newnode newnode.prev=ptr head.prev=newnodeInsertion at a given positionIn this operation a new node is inserted at a given position of CDLL. Given CDLL Create a new node with value 2 Let the new node be inserted at pos=3 Take a variable ptr and let it point to head initially Traverse through the list to make ptr point to the node with position pos-1 Change the pointers as follows newnode->next=ptr->next The modified list. ALGORITHM
CODE SNIPPETdef insertAtGivenPos(pos,value): global head newnode=ListNode(value) if head is None: head=newnode return ptr=head i=1 while i!=pos-1: ptr=ptr.next i+=1 newnode.next=ptr.next newnode.prev=ptr ptr.next.prev=newnode ptr.next=newnodeDeletion at the beginningIn this operation the node at the beginning i.e., node to which head is pointing is deleted. Given CDLL Node to be deleted Take a variable ptr and let it point to head initially Traverse through the list to make ptr point to the last node Change the pointers as follows ptr->next=head->next free(head) head=ptr->next The modified list ALGORITHM
CODE SNIPPETdef deleteAtBeginning(): global head if head is None: print("Deletion not possible") return ptr=head while ptr.next is not head: ptr=ptr.next ptr.next=head.next head.next.prev=ptr del head head=ptr.nextDeletion at the endIn this operation the node at the end i.e., the last node of CDLL is deleted. Given CDLL Node to be deleted Take a variable ptr and let it point to head initially Traverse through the list to make ptr point to the last node Change the pointers as follows ptr->prev->next=head free(ptr) The modified list ALGORITHM
CODE SNIPPETdef deleteAtEnd(): global head if head is None: print("Deletion not possible") return ptr=head while ptr.next is not head: ptr=ptr.next ptr.prev.next=head head.prev=ptr.prev del ptrDeletion at a given positionIn this operation the node at a given position in CDLL is deleted. Given CDLL Node to be deleted at position 3 Take a variable ptr and let it point to head initially Traverse through the list to make ptr point to the node with position pos-1 Make a variable temp to point to ptr's next i.e., the node to be deleted Change the pointers as follows temp->next->prev=ptr free(temp) -The modified list ALGORITHM
CODE SNIPPETdef deleteAtGivenPos(pos): global head if head is None: print("Deletion not possible") return i=1 while i!=pos-1: ptr=ptr.next i+=1 temp=ptr.next temp.next.prev=ptr ptr.next=temp.next del tempTraverseTraversing a data structure means to visit each of its elements exactly once. In this operation each node of the CDLL is visited. Let's understand through an illustration. Given CDLL Take a variable ptr and let it point to head initially Traverse through the list Traverse until ptr points to the last node When visited print each node's value Result: 3 5 7 8ALGORITHM
CODE SNIPPETdef traverse(): global head if head is None: print("List is empty!") return ptr=head while ptr.next is not head: print(ptr.data) ptr=ptr.nextSearchSearch operation is used to know whether an element with a given value exists or not in the data structure. In this operation a target value is searched. Let's understand through an illustration. Given CDLL Let the target to be searched is 5 Take a variable ptr and let it point to head initially While traversing if the node's value is target then search is successful Here 5 is found hence the search is successful
After traversing the entire list if none of the node's value is target then search is unsuccessful ALGORITHM
CODE SNIPPETdef search(target): global head ptr=head found=False while ptr.next is not head: if ptr.data==target: found=True break ptr=ptr.next if found==True: print("target found!") else: print("target not found!")3)CONCLUSIONLet n be the size of Circular Doubly Linked List. 4) ApplicationsApplications of Circular Doubly Linked List are: -Managing songs playlist in media player applications. With this article at OpenGenus, you must have the complete idea of Circular Doubly Linked List. |