# Insertion at End in Doubly Circular Linked List

In this tutorial we will learn how to insert an element at the end of doubly circular linked list. We will see algorithm and program to perform insertion operation in doubly circular linked list at end.

## Algorithm to Insert a Node at End in Doubly Circular Linked List

1. Create a New Node:
• Allocate memory for a new node.
• Set its `data` field to the given value.
• Initially, set the `next` and `prev` pointers of the node to point to itself (this handles the case where the node being added is the first node).
2. Check if the List is Empty:
• If the `head` pointer is `NULL`, the list is empty.
• If the list is empty, set `head` to the new node, making it both the first and last node. The `next` and `prev` of this node will point to itself, maintaining the circular structure.
3. Insert the Node at the End:
• If the list is not empty:
• Find the last node (the node whose `next` points to `head`).
• Set the `next` pointer of the new node to `head`.
• Set the `prev` pointer of `head` to the new node.
• Set the `next` pointer of the last node to the new node.
• Set the `prev` pointer of the new node to the last node.
4. The Node is Inserted:
• The new node is now the last node in the list, and the list still maintains its circular structure.

## Example: Inserting Nodes in a Doubly Circular Linked List at end

Start with an Empty List: Initially, our list is empty. So, `head` is `NULL`.

#### Step 1: Create a New Node (e.g., with value `10`)

• Action: Allocate memory for a new node. Set its `data` field to `10`.
• Initial Pointers: Set both the `next` and `prev` pointers of the node to point to itself.
``[10] <-> [10]  (A self-referencing single-node circular list)``

#### Step 2: Check if the List is Empty

• List is Empty: Since `head` is `NULL`, the list is empty.

#### Step 3: Insert the Node (`10`) at the End

• List is Empty Case:
• Action: Set `head` to the new node.
``head -> [10] <-> [10] (Points to itself)``

#### Step 4: Add Another Node (e.g., with value `20`)

• Create Node: A new node for `20` is created.
• Initial Pointers: The `next` and `prev` of this node point to itself.
``[20] <-> [20]  (A self-referencing node before insertion)``

#### Step 5: Insert the Node (`20`) at the End

• List is Not Empty:
• Find the Last Node: The current last node is `10` (as it’s the only node and `head` points to it).
• Set the `next` pointer of new node (20) to `head` (10).
• Set the `prev` pointer of `head` (10) to new node (20).
• The `next` pointer of the last node (10) is set to new node (20).
• Set the `prev` pointer of new node (20) to last node (10).
• Update Head: `head` still points to the first node (10).
• After Adding Node `20`:
• The list has two nodes `10` and `20`, where `20` is added at the end.
• The list maintains its circular nature.
``````head -> [10] <--> [20]
^------------|``````

This example demonstrates the process of adding nodes to the end of a doubly circular linked list, clearly showing how each node is linked to maintain the circular and doubly linked structure.

## Program in C to Insert a Node at End of Doubly Circular Linked List

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

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

typedef struct Node Node;

// Create 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 insertionAtEnd(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 at End: \n");
do {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
}

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

Output

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

### Explanation of the Program

Struct Node Definition:

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

typedef struct Node 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.