In this tutorial you will learn how to perform node insertion operation in Doubly Circular Linked List. We will also discuss its algorithm and program.
Algorithm to Insert a Node at Beginning in Doubly Circular Linked List
- Create a New Node:
- Allocate memory for a new node. Set its
data
field to the given value. - Initially, set the
next
andprev
pointers of the node to point to itself.
- Allocate memory for a new node. Set its
- Check if the List is Empty:
- If the
head
pointer isNULL
, the list is empty. - If the list is empty, set the
next
andprev
pointers of the new node to point to itself and updatehead
to the new node.
- If the
- Insert the Node at the Beginning:
- If the list is not empty:
- Set the
next
pointer of the new node tohead
. - Set the
prev
pointer ofhead
to the new node. - Find the last node of the list (the node whose
next
points tohead
). - Set the
next
pointer of the last node to the new node. - Set the
prev
pointer of the new node to the last node. - Update
head
to the new node.
- Set the
- If the list is not empty:
- The Node is Inserted:
- The new node is now the first node in the list, and the list maintains its circular structure.
Step By Step Explanation
Here we will se how insertion at the beginning works in Doubly Circular Linked List.
Step 1: Start with an Empty List
Initial State:
head -> NULL
Step 2: Create a New Node with Value 10
- Node Creation:
- A new node with data
10
is created.
- A new node with data
- Initial Pointers:
- The
next
andprev
pointers of this new node point to itself.
- The
[10] <-> [10] (A self-referencing single-node circular list)
Step 3: Insert the New Node (10
) at the Beginning
- List is Empty (head is NULL):
- Insert the node and update
head
to this new node.
- Insert the node and update
head -> [10] <-> [10] (Points to itself)
Step 4: Add Another Node with Value 20
- Node Creation:
- A new node with data
20
is created.
- A new node with data
- Initial Pointers:
- The
next
andprev
of this node initially point to itself.
- The
[20] <-> [20] (A self-referencing node before insertion)
Step 5: Insert the New Node (20
) at the Beginning
- Adjust Pointers:
next
of new node (20) points tohead
(10).prev
ofhead
(10) now points to new node (20).- The
next
of the last node (which is 10 at this moment) points to new node (20). prev
of new node (20) points to the last node (10).
- Update Head:
head
is updated to point to the new node (20).
head -> [20] <--> [10]
^------------|
C Program to Insert a Node at 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 Beginning of the Doubly Circular Linked List
void insertAtBeginning(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 = newNode;
(*head)->prev = newNode;
*head = newNode;
}
}
// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node *head) {
if (head == NULL) {
printf("The list is empty.\n");
return;
}
Node *temp = head;
printf("Doubly Circular Linked List After Insertion at Beginning: \n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
Node *head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
insertAtBeginning(&head, 40);
insertAtBeginning(&head, 50);
printDoublyCircularLinkedList(head);
return 0;
}
Output
Doubly Circular Linked List After Insertion at Beginning: 50 40 30 20 10
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 with data
to store the value, and next
and prev
pointers to point to the next and previous nodes in the list, respectively.
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;
}
This function creates a new node with the given data
. It allocates memory for a Node
, sets its data
, and initializes next
and prev
to point to the node itself. This is useful for handling a single-node circular list.
Function insertAtBeginning
:
// Insert at the Beginning of the Doubly Circular Linked List
void insertAtBeginning(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 = newNode;
(*head)->prev = newNode;
*head = newNode;
}
}
This function inserts a new node at the beginning 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 adjusts the pointers to insert the new node before the current head. It sets newNode->next
to the current head and newNode->prev
to the last node. It also adjusts the previous head and last node to point to the new node. Finally, it updates head
to point to the new node.
Function printDoublyCircularLinkedList
:
// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node *head) {
if (head == NULL) {
printf("The list is empty.\n");
return;
}
Node *temp = head;
printf("Doubly Circular Linked List After Insertion at Beginning: \n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
This function prints the elements of the doubly circular linked list starting from the head
.
It traverses the list from head
, printing each node’s data
, until it completes a full cycle and returns to the head
, indicating one full traversal of the circular list.
main
Function:
int main() {
Node *head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
insertAtBeginning(&head, 40);
insertAtBeginning(&head, 50);
printDoublyCircularLinkedList(head);
return 0;
}
Initializes a head
pointer to NULL
, indicating an empty list.
Calls insertAtBeginning
five times to insert numbers 10, 20, 30, 40 and 50 at the beginning of the list.
Finally, calls printDoublyCircularLinkedList
to display the list.
Hope this post helped you to understand how to insert node at beginning in Doubly Circular Linked List.
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…