**INTRODUCTION**

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by previous pointer.

This is the basic structure of a circular doubly linked list.

Following is representation of a Circular doubly linked list node in C/C++:

struct node

{

int data;

struct node *next; // Pointer to next node

struct node *prev; // Pointer to previous node

};

And to implement a circularly doubly linked lists, the steps followed are mentioned below:

1. Form a basic structure of a node which contains three parts ; The data as the node, the next and previous pointer.

2. Create the node using the function create_node() which takes a value x and creates the node.

3. Sort the list using traverse_head() to show output in forward direction and the function traverse_tail() to show output in reverse direction.

Following is a complete program that uses all of the above methods to create a sorted circular doubly linked list.

**PROGRAM**

using namespace std;

template <typename T>

struct Value

{

T m_Value;

Value()

{

m_Value = 0; //Default Constructor Called

}

};

template<typename T>

struct Value1

{

T m_Value;

Value1(T x1)

{

m_Value=x1; //Parameterized Constructor called

}

};

struct node

{

int data;

node *next;

node *prev;

}*p = NULL, *head = NULL, *r = NULL, *nullpoint = NULL, *tail = NULL;

int c = 0;

template <typename T>

T create_node(T x) //template based function to create a node.

{

nullpoint = new node;

nullpoint->data = x;

nullpoint->next = NULL;

nullpoint->prev = NULL;

if (c == 0)

{

tail = nullpoint;

head = nullpoint;

p = head;

p->next = head;

p->prev = head;

c++;

}

else if (c == 1)

{

p = head;

r = p;

if (nullpoint->data < p->data)

{

nullpoint->next = p;

p->prev = nullpoint;

head = nullpoint;

p->next = nullpoint;

nullpoint->prev = p;

tail = p;

}

else if (nullpoint->data > p->data)

{

p->next = nullpoint;

nullpoint->prev = p;

nullpoint->next = head;

p->prev = nullpoint;

}

c++;

} else

{

p = head;

r = p;

if (nullpoint->data < p->data)

{

nullpoint->next = p;

p->prev = nullpoint;

head = nullpoint;

do

{

p = p->next;

}

while (p->next != r);

tail = p;

p->next = nullpoint;

nullpoint ->prev = p;

}

else if (nullpoint ->data > p->data)

{

while (p->next != head && nullpoint->data > p->data)

{

r = p;

p = p->next;

if (p->next == head && (p->data < nullpoint->data))

{

p->next = nullpoint;

nullpoint->prev = p;

nullpoint->next = head;

tail = nullpoint;

head->prev = nullpoint;

break;

}

else if (nullpoint->data < p->data)

{

r->next = nullpoint;

nullpoint->prev = r;

nullpoint->next = p;

p->prev = nullpoint;

if (p->next != head)

{

do

{

p = p->next;

}

while (p->next != head);

}

tail = p;

break;

}

}

}

}

}

template <typename T>

T traverse_tail(T i)

{

node *t = tail;

int x = 0;

while (x <= i)

{

cout<<t->data<<" ";

t = t->prev;

x++;

}

cout<<endl;

}

template <typename T>

T traverse_head(T i)

{

node *t = head;

int c = 0;

while (c <= i)

{

cout<<t->data<<" ";

t = t->next;

c++;

}

cout<<endl;

}

int main(void)

{

int i = 0, n, x;

cout<<"Enter the number of nodes of a Linked List"<<endl;

cin>>n;

while (i < n)

{

cout<<"\nEnter the value of a node in Linked List"<<endl;

cin>>x;

create_node(x);

i++;

}

cout<<"\nSorted Doubly Linked List "<<endl;

traverse_head(n);

cout<<"\nSorted Doubly Linked List(Reverse) "<<endl;

traverse_tail(n);

}

**OUTPUT:-**

Name | Views | Likes |
---|---|---|

C++ Program to Implement Sorted Circularly Doubly Linked List | 284 | 17 |

## Comments