# Creation and Insertion in Doubly Circular Linked List : Algo and Program

In this tutorial we will learn how to create doubly circular linked list. We will see the algorithm and program to create doubly circular linked list.

## Algorithm to Create Doubly Circular Linked List

• Initialize the `head` pointer to `NULL`. This will indicate that the list is initially empty.
• `head -> NULL`
2. Create a New Node:
• When adding a new element, create a new node.
• Allocate memory for the node and set its `data` field.
• Initially, set the `next` and `prev` pointers of the node to point to itself. This sets up the circular structure for a single-node list.
3. Insert the New Node:
• If the list is empty (i.e., `head` is `NULL`), set `head` to the new node.
• If the list is not empty, insert the new node at the end (or any other preferred position):
• Link the new node with the existing nodes by adjusting the `next` and `prev` pointers.
• Ensure the last node’s `next` points to the new node and the new node’s `prev` points to the last node.
• Update the `next` pointer of the new node to point to `head` and the `prev` pointer of `head` to point to the new node.
4. Repeat for More Nodes:
• Repeat the process for each new element you want to add to the list.

## Example to Demonstrate the Algorithm

• Initial State: We begin with an empty list. So, `head` is initialized to `NULL`.
• Visualization: `head -> NULL`

#### 2. Create a New Node

• Add Element: Suppose we want to add `10` to the list.
• Action: A new node is created with `data = 10`. The `next` and `prev` pointers of this node point to itself.
• Node State: `[Prev: itself | Data: 10 | Next: itself]`

#### 3. Insert the New Node

• List is Empty (head is NULL): Since the list is empty, `head` is set to this new node.
• The list now contains one node, which points to itself, forming a circular structure.

• Add Element: Let’s add another element, say `20`.
• Create Node: A new node for `20` is created.
• Node State: `[Prev: itself | Data: 20 | Next: itself]`
• Insertion: Since the list is not empty:
• The `next` of the new node (20) points to `head` (10).
• The `prev` of `head` (10) points to the new node (20).
• The `next` of the last node (10) points to the new node (20).
• The `prev` of the new node (20) points to the last node (10).

Similar we can add any number of nodes in the doubly circular linked list.

## C Program to Create and Insert in Doubly Circular Linked List

``````#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node Node;

// reate a new node
Node *createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}

// Insert at the end of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
Node *newNode = createNode(data);
} else {
newNode->prev = last;
last->next = newNode;
}
}

// Print the Doubly Circular Linked List
printf("Doubly Circular Linked List is empty.\n");
return;
}
printf("Doubly Circular Linked List After Insertion: \n");
do {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
}

int main() {
return 0;
}
``````

Output

```Doubly Circular Linked List After Insertion:
10 20 30 40 50 60```

### Explanation of the Program

Struct Node Definition

``````typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;``````

A `struct Node` is defined, containing an integer `data` and two pointers `next` and `prev`, pointing to the next and previous nodes in the list, respectively.

Function `createNode`:

``````// reate a new node
Node *createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}``````

This function creates a new node with the given data. It allocates memory for a new `Node`, sets its `data` field, and initializes both `next` and `prev` pointers to point to the node itself. This self-referencing setup is useful for handling a single-node circular list.

Function `insertAtEnd`:

``````// Insert at the end of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
Node *newNode = createNode(data);
} else {
newNode->prev = last;
last->next = newNode;
}
}``````

This function inserts a new node at the end of the doubly circular linked list.

If the list is empty (`*head == NULL`), the new node becomes the `head` of the list.

If the list is not empty, it finds the last node (the node before `head`) and inserts the new node between the last node and `head`, updating the `next` and `prev` pointers appropriately to maintain the circular nature of the list.

Function `printDoublyCircularLinkedList`:

``````// Print the Doubly Circular Linked List
printf("Doubly Circular Linked List is empty.\n");
return;
}
printf("Doubly Circular Linked List After Insertion: \n");
do {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
}``````

This function prints the elements of the doubly circular linked list starting from `head`.

It traverses the list starting from `head` and keeps printing the `data` of each node until it reaches the `head` again, indicating one full cycle through the circular list.

`main` Function:

``````int main() {
A `head` pointer is initialized to `NULL`, indicating an empty list.
The `insertAtEnd` function is called six times to insert the numbers 10, 20, 30, 40, 50, and 60 at the end of the list.
Finally, `printDoublyCircularLinkedList` is called to display the list.