# Delete a Node at End of Doubly Circular Linked List

In this tutorial we will learn writing Algorithm and Program to delete a node from beginning on Doubly Circular Linked List.

## Algorithm to Delete a Node at the End of Doubly Circular Linked List

1. Check if the List is Empty:
• If the `head` pointer is `NULL`, it means the list is empty. Print a message indicating that deletion is not possible and exit the function.
2. Single Node Case:
• If the list has only one node (i.e., `head->next` is `head`), delete `head`, set it to `NULL`, and exit.
3. Multiple Nodes Case:
• If the list contains more than one node:
• Find the second-to-last node (the node whose `next` pointer points to `head`).
• Update its `next` pointer to `head`, effectively removing the last node from the list.
• Update the `prev` pointer of `head` to point to this new last node.
• Delete the original last node.
4. Completion:
• The last node is removed from the list, and the list still maintains its circular structure.

## Example

• Given List: A Doubly Circular Linked List with elements: 10, 20, 30, 40.
• Task: Delete the last node (which contains the element `40`).

#### Initial State of the List

• List: `head -> [10] <-> [20] <-> [30] <-> [40] <-> back to [10]`

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

• Check: Since `head` is not `NULL`, the list is not empty.

#### Step 2: Single Node Case

• Determine: The list has more than one node, so this step is not applicable.

#### Step 3: Multiple Nodes Case

• Find the Second-to-Last Node
• Start from `head` (node `[10]`).
• Move to the next nodes until reaching the node `[30]`, which is the second-to-last node as its `next` is `[40]` (the last node).
• Update Pointers
• Set the `next` of `[30]` to `head` (`[10]`).
• Update the `prev` pointer of `head` (`[10]`) to point to `[30]`.
• Delete the Last Node
• Remove node `[40]` and free its memory.

#### Completion

• Final State of the List: `head -> [10] <-> [20] <-> [30] <-> back to [10]`
• The node containing `40` is successfully removed.
• The list still maintains its circular structure.

### Conclusion

• Outcome: The last node (`[40]`) has been deleted from the list.

## C Program to delete from 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 insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
} else {
newNode->prev = last;
}
}

// Delete a node from End
printf("List is empty. No node to delete.\n");
return;
}
} else {
Node* newLast = toDelete->prev;
}
free(toDelete);
printf("Node deleted from the end.\n");
}

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

int main() {
printf("Doubly Circular Linked List Before Deletion:\n");

printf("Doubly Circular Linked List After Deletion:\n");

return 0;
}
``````

Output

```Doubly Circular Linked List Before Deletion:
Doubly Circular Linked List: 10 20 30 40 50
Node deleted from the end.
Doubly Circular Linked List After Deletion:
Doubly Circular Linked List: 10 20 30 40```

### Program Explanation

#### Node Structure Definition

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

typedef struct Node Node;``````
• Defines a `Node` structure for each element in the DCLL.
• Contains:
• `int data`: The integer value stored in the node.
• `struct Node* next`: A pointer to the next node in the list.
• `struct Node* prev`: A pointer to the previous node in the list.
• The `typedef` keyword in C is used to create an alias for a data type. The statement `typedef struct Node Node;` creates an alias `Node` for `struct Node`.

#### Function: createNode

``````// 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;
}``````
• Purpose: Creates a new node with the specified data.
• Process:
• Allocates memory for a new `Node`.
• Initializes the node’s `data` with the given value.
• Points `next` and `prev` to the node itself (crucial for a 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;
}
}``````
• Purpose: Inserts a new node at the end of the DCLL.
• Process:
• If the list is empty (`*head == NULL`), sets the new node as `head`.
• If not, finds the current last node (`(*head)->prev`).
• Inserts the new node between the last node and the head.
• Adjusts `next` and `prev` pointers of relevant nodes to maintain the circular structure.

#### Function: deleteFromEnd

``````// Delete a node from End
printf("List is empty. No node to delete.\n");
return;
}
} else {
Node* newLast = toDelete->prev;
}
free(toDelete);
printf("Node deleted from the end.\n");
}``````
• Purpose: Deletes the last node from the DCLL.
• Process:
• Checks if the list is empty. If so, prints a message and exits.
• Identifies the node to delete (`(*head)->prev`).
• If this node is the only node in the list, sets `head` to `NULL`.
• If there are multiple nodes, adjusts the `next` of the second-to-last node and the `prev` of `head` to bypass the last node.
• Frees the memory allocated to the last node.

``````// Print the Doubly Circular Linked List
printf("Doubly Circular Linked List is empty.\n");
return;
}
do {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
}``````
• Purpose: Prints the contents of the DCLL.
• Process:
• Checks if the list is empty. If so, prints a message and exits.
• Traverses the list from `head`, printing the `data` of each node, until it reaches `head` again.

#### Main Function

``````int main() {
printf("Doubly Circular Linked List Before Deletion:\n");

printf("Doubly Circular Linked List After Deletion:\n");

return 0;
}``````
• Functionality:
• Initializes an empty DCLL (`head = NULL`).
• Inserts several nodes at the end of the list (with values 10, 20, 30, 40, 50).
• Prints the list before deletion.
• Deletes the last node.
• Prints the list after deletion to show the updated list.

#### Output of the Program

• Initially, the program will display the DCLL with nodes containing 10, 20, 30, 40, 50.
• After executing `deleteFromEnd`, the last node (containing 50) will be removed. The program then displays the updated list: 10, 20, 30, 40.

Hope this article helped you in understanding the writing Program and Algorithm to perform delete operation from end on Doubly Circular Linked List.