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:

- 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 8**#### ALGORITHM

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.