Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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:
- Introduction to Circular Doubly Linked List
- Insertion at the beginning
- Insertion at the end
- Insertion at a given position
- Deletion at the beginning
- Deletion at the end
- Deletion at a given position
- Traverse
- Search
- Applications
Pre-requisites:
1) Introduction to Circular Doubly Linked List
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=None
Various operations can be performed on Circular Doubly Linked List as discussed below.
Insertion at the beginning
In 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
-Last node's next pointer will point to new node as it'll be new head.
newnode->prev=ptr
-New node's prev pointer will point to ptr as head's previous must be last node.
newnode->next=head
-New node's next pointer will point to current head as current head'll become the second node.
head->prev=newnode
-Current head's prev pointer will point to new node as it'll be the new head now.
head=newnode
-Finally head pointer will point to the new node.
-The modified list
ALGORITHM
STEP-1: Create newnode
STEP-2: SET ptr=head
STEP-3: Repeat STEP-4 while ptr->next!=head
STEP-4: βSET ptr=ptr->next
ββββ[END OF LOOP]
STEP-5: SET ptr->next=newnode
STEP-6: SET newnode->prev=ptr
STEP-7: SET newnode->next=head
STEP-8: SET head->prev=newnode
STEP-9: SET head=newnode
STEP-10: EXIT
CODE SNIPPET
def 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=newnode
Insertion at the end
In 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
-New node's next pointer will point to head as it'll become the last node.
ptr->next=newnode
-Current last node's next pointer will point to new node as it'll become the second last node now.
newnode->prev=ptr
-New node's prev pointer will point to current last node.
head->prev=newnode
-Head's prev pointer will point to new node as new node will become the last node.
The modified list.
ALGORITHM
STEP-1: Create newnode
STEP-2: SET ptr=head
STEP-3: Repeat STEP-4 while ptr->next!=head
STEP-4: βSET ptr=ptr->next
ββββ[END OF LOOP]
STEP-5: SET newnode->next=head
STEP-6: SET ptr->next=newnode
STEP-7: SET newnode->prev=ptr
STEP-8: SET head->prev=newnode
STEP-9: EXIT
CODE SNIPPET
def 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=newnode
Insertion at a given position
In this operation a new node is inserted at a given position of CDLL.
Let's understand through an illustration.
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
-new node's next pointer will point to ptr's next
newnode->prev=ptr
-new node's prev pointer will point to ptr as ptr will be before new node.
ptr->next->prev=newnode
-ptr's next i,e., the node which will be after new node.Its prev pointer will point to new node as new node will be before it.
ptr->next=newnode
-ptr's prev pointer will point to new node as new node will be after it.
The modified list.
ALGORITHM
STEP-1: Create newnode
STEP-2: SET ptr=head
STEP-3: SET i=1
STEP-4: Repeat STEPS-5 to 6 while i!=pos-1
STEP-5: βSET ptr=ptr->next
STEP-6: βSET i=i+1
ββββ[END OF LOOP]
STEP-7: SET newnode->next=ptr->next
STEP-8: SET newnode->prev=ptr
STEP-9: SET ptr->next->prev=newnode
STEP-10: SET ptr->next=newnode
STEP-11: EXIT
CODE SNIPPET
def 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=newnode
Deletion at the beginning
In this operation the node at the beginning i.e., node to which head is pointing is deleted.
Let's understand through an illustration.
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
-last node's next pointer will point to head's next as current head's next will become the new head
head->next->prev=ptr
-prev pointer of head's next, which will become the new head ,will point to last node.
free(head)
-Free the memory allocated to current head
head=ptr->next
-Change head to ptr's next as it points to the new head
The modified list
ALGORITHM
STEP-1: SET ptr=head
STEP-2: Repeat STEP-3 while ptr->next!=head
STEP-3: βSET ptr=ptr->next
ββββ[END OF LOOP]
STEP-4: SET ptr->next=head->next
STEP-5: SET head->next->prev=ptr
STEP-6: free(head)
STEP-7: SET head=ptr->next
STEP-8: EXIT
CODE SNIPPET
def 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.next
Deletion at the end
In this operation the node at the end i.e., the last node of CDLL is deleted.
Let's understand through an illustration.
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
-next pointer of last node's prev will point to head as last node will become the last node.
head->prev=ptr->prev
-ptr's prev node will become the last node.Hence, head's prev pointer will point to it.
free(ptr)
-Free the memory allocated to current last node
The modified list
ALGORITHM
STEP-1: SET ptr=head
STEP-2: Repeat STEP-3 while ptr->next!=head
STEP-3: βSET ptr=ptr->next
ββββ[END OF LOOP]
STEP-4: SET ptr->prev->next=head
STEP-5: SET head->prev=ptr->prev
STEP-6: free(ptr)
STEP-7: EXIT
CODE SNIPPET
def 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 ptr
Deletion at a given position
In this operation the node at a given position in CDLL is deleted.
Let's understand through an illustration.
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
-prev pointer of temp's next will point to ptr
ptr->next=temp->next
-ptr's next pointer will point to temp's next
free(temp)
-Free the memory allocated to node pointed by temp
-The modified list
ALGORITHM
STEP-1: SET ptr=head
STEP-2: SET i=1
STEP-3: Repeat STEPS-4 to 5 while i!=pos-1
STEP-4: βSET ptr=ptr->next
STEP-5: βSET i=i+1
ββββ[END OF LOOP]
STEP-6: SET temp=ptr->next
STEP-7: SET temp->next->prev=ptr
STEP-8: SET ptr->next=temp->next
STEP-9: free(temp)
STEP-10: EXIT
CODE SNIPPET
def 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 temp
Traverse
Traversing 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
STEP-1: SET ptr=head
STEP-2: Repeat STEPS-3 to 4 while ptr->next!=head
STEP-3: βPRINT ptr->data
STEP-4: βSET ptr=ptr->next
ββββ[END OF LOOP]
STEP-5: EXIT
CODE SNIPPET
def 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.next
Search
Search 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
STEP-1: SET ptr=head
STEP-2: SET found=false
STEP-3: Repeat STEPS-4 to 8 while ptr->next!=head
STEP-4: βIF ptr->data=target
STEP-5: ββPRINT ptr->data
STEP-6: ββfound=true
STEP-7: ββGo to STEP-9
βββββ[END OF IF]
STEP-8: βSET ptr=ptr->next
ββββ[END OF LOOP]
STEP-9: IF found=true
ββββββββPRINT "target found!"
STEP-10: ELSE
ββββββββPRINT "target not found!"
ββββ[END OF IF]
STEP-11: EXIT
CODE SNIPPET
def 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)CONCLUSION
Let n be the size of Circular Doubly Linked List.
Each of the above discussed operations takes O(n) time complexity.
4) Applications
Applications of Circular Doubly Linked List are:
-Managing songs playlist in media player applications.
-Managing shopping cart in online shopping.
With this article at OpenGenus, you must have the complete idea of Circular Doubly Linked List.