Circular Doubly Linked List(CDLL)

• Circular Doubly linked list(CDLL) is the extended version of simple Doubly linked list.
• It is something complex data structure ,because there are a lot of pointer operation need to be do for any operation.
• prevNode Pointer of first Node and nextNode Pointer of Last node will not set by NULL in CDLL.
• nextNode Pointer of Last node will always point to the first node in CDLL.
• prevNode Pointer of First node will always point to the last node in CDLL.
• Similar to the Doubly Linked list CDLL also provide an Double directional operation.
• There is one HeadPointer which always points to the first node.HeadPointer have alot of benefits.

Structure of Circular Linked List is Following :

Example :

Node Representation

• Similr to the Doubly linked list(DLL) ,In Circular Doubly Linked List(CDLL) ,Node is the collection of Data Element and Pointer variable for next Node and previous node.
• We can implement Node in C and C++ by the using of the structure User-define data type.

struct CreateNode
{
    int DataElement;    // for storing the DataElement
    struct CreateNode* nextNode;  // for pointing the next node.
    struct CreateNode* PreNode;  // for pointing the Previous node.
}

Operations of Circular Doubly Linked List(CDLL)

There are following operations ,we can apply on Circular Doubly linked list :

• Insertion of node at beginning(front) in CDLL.
• Insertion of node at last(end) in CDLL.
• Insertion of node at specific location in CDLL.
• Deletion of node at beginning(front) in CDLL.
• Deletion of node at last(end) in CDLL.
• Deletion of node at specific location in CDLL.
• Searching in CDLL.

---

Insertion of node at beginning(front) in CDLL :

• Time Complexity will be O(1).
• Space Complexity will be O(1).

Insertion of node at last(end) in CDLL :

• Time Complexity will be O(1).
• Space Complexity will be O(1).

Insertion of node at specific location in CDLL :

• Worst Case Time Complexity will be O(n).
• Best Case Time Complexity will be O(1).
• Average Case Time Complexity will be O(n).
• Space Complexity will be O(1).

Deletion of node at beginning(front) in CDLL :

• Time Complexity will be O(1).
• Space Complexity will be O(1).

Deletion of node at last(end) in CDLL :

• Time Complexity will be O(1).
• Space Complexity will be O(1).

Deletion of node at specific location in CDLL :

• Worst Case Time Complexity will be O(n).
• Best Case Time Complexity will be O(1).
• Average Case Time Complexity will be O(n).
• Space Complexity will be O(1).

Searching in CDLL :

• Worst Case Time Complexity will be O(n).
• Best Case Time Complexity will be O(1).
• Average Case Time Complexity will be O(n).
• Space Complexity will be O(1).

---

Advantage of CDLL

• Traversing is allowed from both side means we can traverse the whole list from Head to Tail and Tail to Head.
• CDLL is generally use to implement Advanced data structure like Fibonacci Heap.

Disadvantage of CDLL

• Space required for all the node for storing the address of next and previous node.
• For every operation we require more time to complete because more pointer operation is needed.
• We have to careful for the data element otherwise data may be lost because of more pointer operation.

Applications of CDLL

• CDLL can be use to implement the LRU(Least Recently Used) and MRU(Most recently used) in Operating system.
• Backward and forward navigation of browser can be implement using DLL.
• Can be used to implement for the circular operations like :
  Song Playlist, Image Viewer,Slider etc.