In this tutorial we will learn writing Algorithm and Program to delete a node from beginning on Doubly Circular Linked List.
Algorithm to Delete Node from Beginning of Doubly Circular Linked List
- Check if the List is Empty:
- If the
head
pointer isNULL
, the list is empty. Indicate that deletion is not possible.
- If the
- Single Node Case:
- If the list has only one node (i.e.,
head->next
ishead
), deletehead
and set it toNULL
.
- If the list has only one node (i.e.,
- Multiple Nodes Case:
- If the list contains more than one node:
- Update the
next
pointer of the last node to point to the second node in the list (head->next
). - Set the
prev
pointer of the second node to point to the last node. - Delete the first node (
head
). - Update
head
to the second node.
- Update the
- If the list contains more than one node:
- The First Node is Deleted:
- The list’s first node is removed, and the list still maintains its circular structure.
Example
- Given List: Imagine we have a Doubly Circular Linked List with the elements: 10, 20, 30.
- Task: We want to delete the first node (which currently has the data
10
).
Steps
Initial State of the List
- List:
head -> [10] <-> [20] <-> [30] <-> back to [10]
Step 1: Check if the List is Empty
- Check:
head
is notNULL
, so the list is not empty.
Step 2: Single Node Case
- Determine: In this example, the list has more than one node, so this step is not applicable.
Step 3: Multiple Nodes Case
- Let’s delete the first node
[10]
:- Find Last Node: In this case, it’s the node
[30]
. - Update Pointers:
- Set
[30]->next
to[20]
(which ishead->next
). - Set
[20]->prev
to[30]
.
- Set
- Delete First Node:
- Remove
[10]
and free its memory.
- Remove
- Update Head:
- Set
head
to[20]
.
- Set
- Find Last Node: In this case, it’s the node
Final State of the List
- List After Deletion:
head -> [20] <-> [30] <-> back to [20]
The First Node is Deleted
- The node containing
10
is successfully removed. - The list still maintains its circular structure.
Conclusion
- Outcome: The first node (
[10]
) is deleted, and the new head of the list is the node[20]
.
C Program to Delete a Node from the Beginning of a 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);
if (*head == NULL) {
*head = newNode;
} else {
Node* last = (*head)->prev;
newNode->next = *head;
newNode->prev = last;
last->next = (*head)->prev = newNode;
}
}
// Delete the Doubly Circular Linked List From Beginning
void deleteFromBeginningInDCLL(Node** head) {
if (*head == NULL) {
printf("List is empty. No node to delete.\n");
return;
}
Node* toDelete = *head;
if ((*head)->next == *head) {
*head = NULL;
} else {
Node* last = (*head)->prev;
*head = (*head)->next;
(*head)->prev = last;
last->next = *head;
}
free(toDelete);
printf("Node deleted from the beginning.\n");
}
// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node* head) {
if (!head) {
printf("The list is empty.\n");
return;
}
Node* temp = head;
printf("Doubly Circular Linked List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
insertAtEnd(&head, 40);
insertAtEnd(&head, 50);
insertAtEnd(&head, 60);
printf("Doubly Circular Linked List Before Deletion:\n");
printDoublyCircularLinkedList(head);
deleteFromBeginningInDCLL(&head);
printf("Doubly Circular Linked List After Deletion:\n");
printDoublyCircularLinkedList(head);
return 0;
}
Output
Doubly Circular Linked List Before Deletion: Doubly Circular Linked List: 10 20 30 40 50 60 Node deleted from the beginning. Doubly Circular Linked List After Deletion: Doubly Circular Linked List: 20 30 40 50 60
Explanation of the above program
Node Structure Definition
struct Node {
int data;
struct Node *next;
struct Node *prev;
};
typedef struct Node Node;
- Defines a structure
Node
for each element in the doubly circular linked list. - Each
Node
contains:int data
: The 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 statementtypedef struct Node Node;
creates an aliasNode
forstruct Node
.
Function: createNode
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 given data.
- Process:
- Allocates memory for the new node.
- Initializes the node’s
data
field. - Sets the
next
andprev
pointers to point to the node itself. This is key for maintaining the circular nature of the list, particularly when the node is the only one in the list.
Function: insertAtEnd
void insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* last = (*head)->prev;
newNode->next = *head;
newNode->prev = last;
last->next = (*head)->prev = newNode;
}
}
- Purpose: Inserts a new node at the end of the doubly circular linked list.
- Process:
- If the list is empty (
*head == NULL
), the new node becomes the head. - If the list is not empty:
- Identifies the last node (the one before the head).
- Inserts the new node between the last node and the head, updating the
next
andprev
pointers to maintain the circular structure.
- If the list is empty (
Function: deleteFromBeginningInDCLL
void deleteFromBeginningInDCLL(Node** head) {
if (*head == NULL) {
printf("List is empty. No node to delete.\n");
return;
}
Node* toDelete = *head;
if ((*head)->next == *head) {
*head = NULL;
} else {
Node* last = (*head)->prev;
*head = (*head)->next;
(*head)->prev = last;
last->next = *head;
}
free(toDelete);
printf("Node deleted from the beginning.\n");
}
- Purpose: Deletes the first node of the doubly circular linked list.
- Process:
- If the list is empty, it indicates that there are no nodes to delete.
- If the list has only one node (where
head->next
ishead
), deletes the head and sets it toNULL
. - In case of multiple nodes, it updates the
next
pointer of the last node to the second node and theprev
pointer of the second node to the last node, then deletes the first node (head
).
Function: printDoublyCircularLinkedList
void printDoublyCircularLinkedList(Node* head) {
if (!head) {
printf("The list is empty.\n");
return;
}
Node* temp = head;
printf("Doubly Circular Linked List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
- Purpose: Prints the elements of the doubly circular linked list.
- Process:
- Starts from the head and traverses the list by following the
next
pointers, printing each node’s data until it cycles back to the head.
- Starts from the head and traverses the list by following the
Main Function
int main() {
Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf("Before Deletion:\n");
printList(head);
deleteFromBeginning(&head);
printf("After Deletion:\n");
printList(head);
return 0;
}
- Purpose: Demonstrates the functionality of the list.
- Process:
- Initializes an empty list (
head = NULL
). - Inserts several nodes at the end of the list.
- Prints the list before and after deleting the first node to show the effect of the
deleteFromBeginningInDCLL
function.
- Initializes an empty list (
Hope above program and algorithm helped you to understand how to delete from beginning on Doubly Circular Linked List
What did you think?
Similar Reads
-
Multiplications of Two variable polynomial
Polynomial multiplication is a common operation in algebra, used in areas such as scientific computing, engineering simulations, and symbolic algebra… -
Subtraction of Two-Variable Polynomial in C
Polynomials with two variables are common in engineering, graphics, and scientific computation. While addition is frequently discussed, subtraction is equally… -
Explain the Addition of Two variable polynomial
Polynomials are fundamental in mathematics, and their use extends into computer science, engineering, physics, and more. While single-variable polynomials are… -
Reverses the Doubly Circular Linked List
Algorithm to Reverse a Doubly Circular Linked List Check if the List is Empty or Has Only One Node: If… -
Algorithm and Program in C to traverse Doubly Circular Linked List
A doubly circular linked list is a special type of linked list in which every node is connected to both… -
Polynomial representation Using Array
Polynomials are fundamental mathematical expressions used extensively in various fields. Representing them efficiently in programming is crucial for calculations and… -
Multiplication of Single Variable Polynomial : Algorithm and Program
Multiplication of single-variable polynomials is a fundamental operation in polynomial algebra. The process involves multiplying each term of one polynomial… -
Subtraction of Single variable Polynomial : Algorithm and Program
Subtracting single-variable polynomials involves reducing each corresponding term of the polynomials from each other. This process is similar to addition,… -
Addition of Single variable Polynomial : Program and Algorithm
The addition of single-variable polynomials is a fundamental concept in algebra, often encountered in mathematics and computer science. Let's break… -
Polynomial Representation Using Linked List
Polynomial representation using linked lists is a critical concept in computer science and mathematics. In this guide, we explore how…