Write a c program to Create a Circular single Linked list and perform Following Operations A. Insertion After a particular node B. Insertion Before a particular node C. Search a particular node D. Return a particular node E. Deletion before a particular node F. Delete a particular node
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to create a new node with given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
*head = newNode;
}
}
// Function to insert a node at the end of the circular linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
}
// Function to insert a node after a particular node
void insertAfterNode(struct Node* prevNode, int data) {
if (prevNode == NULL) {
printf("The given previous node cannot be NULL\n");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// Function to insert a node before a particular node
void insertBeforeNode(struct Node** head, int beforeData, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
printf("List is empty\n");
return;
}
if ((*head)->data == beforeData) {
insertAtBeginning(head, data);
return;
}
struct Node* temp = *head;
while (temp->next != *head && temp->next->data != beforeData) {
temp = temp->next;
}
if (temp->next == *head) {
printf("Node with data %d not found\n", beforeData);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to insert a node at a specific position
void insertAtPosition(struct Node** head, int position, int data) {
if (position < 1) {
printf("Position should be >= 1\n");
return;
}
if (position == 1) {
insertAtBeginning(head, data);
return;
}
struct Node* newNode = createNode(data);
struct Node* temp = *head;
for (int i = 1; temp->next != *head && i < position - 1; i++) {
temp = temp->next;
}
if (temp->next == *head && position > 1) {
printf("Position out of range\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to search for a particular node
int searchNode(struct Node* head, int data) {
struct Node* temp = head;
int position = 1;
if (head == NULL) return -1;
do {
if (temp->data == data) {
return position;
}
temp = temp->next;
position++;
} while (temp != head);
return -1; // Not found
}
// Function to return a particular node by its position
struct Node* getNodeByPosition(struct Node* head, int position) {
if (position < 1) {
printf("Position should be >= 1\n");
return NULL;
}
struct Node* temp = head;
int currentPos = 1;
if (head == NULL) return NULL;
do {
if (currentPos == position) {
return temp;
}
temp = temp->next;
currentPos++;
} while (temp != head);
printf("Position out of range\n");
return NULL;
}
// Function to delete a node at the beginning
void deleteAtBeginning(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
struct Node* end = *head;
while (end->next != *head) {
end = end->next;
}
if (temp->next == *head) { // Only one node
*head = NULL;
free(temp);
return;
}
end->next = temp->next;
*head = temp->next;
free(temp);
}
// Function to delete a node at the end
void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->next != *head) {
prev = temp;
temp = temp->next;
}
if (temp == *head) { // Only one node
*head = NULL;
free(temp);
return;
}
prev->next = *head;
free(temp);
}
// Function to delete a node after a particular node
void deleteAfterNode(struct Node* prevNode) {
if (prevNode == NULL || prevNode->next == NULL) {
printf("The given node is invalid or it has no next node\n");
return;
}
struct Node* temp = prevNode->next;
prevNode->next = temp->next;
free(temp);
}
// Function to delete a node before a particular node
void deleteBeforeNode(struct Node** head, int beforeData) {
if (*head == NULL || (*head)->next == NULL) {
printf("List is empty or has only one node\n");
return;
}
if ((*head)->data == beforeData) {
printf("No node exists before the first node\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->next != *head && temp->next->data != beforeData) {
prev = temp;
temp = temp->next;
}
if (temp->next == *head) {
printf("Node with data %d not found\n", beforeData);
return;
}
if (prev == NULL) {
*head = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
}
// Function to delete a particular node by its data
void deleteNode(struct Node** head, int data) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->data != data) {
if (temp->next == *head) {
printf("Node with data %d not found\n", data);
return;
}
prev = temp;
temp = temp->next;
}
if (temp == *head && temp->next == *head) { // Only one node
*head = NULL;
free(temp);
return;
}
if (temp == *head) { // Node to delete is the head
prev = *head;
while (prev->next != *head) {
prev = prev->next;
}
*head = temp->next;
prev->next = *head;
free(temp);
} else if (temp->next == *head) { // Node to delete is the last node
prev->next = *head;
free(temp);
} else { // Node to delete is in the middle
prev->next = temp->next;
free(temp);
}
}
// Function to delete a node at a specific position
void deleteAtPosition(struct Node** head, int position) {
if (*head == NULL || position < 1) {
printf("List is empty or invalid position\n");
return;
}
struct Node* temp = *head;
if (position == 1) {
deleteAtBeginning(head);
return;
}
struct Node* prev = NULL;
for (int i = 1; temp->next != *head && i < position; i++) {
prev = temp;
temp = temp->next;
}
if (temp->next == *head && position > 1) {
printf("Position out of range\n");
return;
}
prev->next = temp->next;
free(temp);
}
// Function to print the circular linked list
void printList(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(head)\n");
}
int main() {
struct Node* head = NULL;
// Sample operations
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 4);
insertAtEnd(&head, 5);
insertAtPosition(&head, 3, 3); // Insert 3 at position 3
insertAtBeginning(&head, 0); // Insert 0 at the beginning
printf("Initial list: ");
printList(head);
printf("After inserting 6 at the end: ");
insertAtEnd(&head, 6);
printList(head);
printf("After inserting 7 at position 4: ");
insertAtPosition(&head, 4, 7);
printList(head);
printf("After inserting 8 before node with data 3: ");
insertBeforeNode(&head, 3, 8);
printList(head);
printf("After deleting node at position 2: ");
deleteAtPosition(&head, 2);
printList(head);
printf("After deleting node with data 5: ");
deleteNode(&head, 5);
printList(head);
printf("After deleting node at the beginning: ");
deleteAtBeginning(&head);
printList(head);
printf("After deleting node at the end: ");
deleteAtEnd(&head);
printList(head);
printf("Searching for node with data 4: ");
int position = searchNode(head, 4);
if (position != -1) {
printf("Node found at position %d\n", position);
} else {
printf("Node not found\n");
}
struct Node* node = getNodeByPosition(head, 3);
if (node != NULL) {
printf("Node at position 3 has data: %d\n", node->data);
}
return 0;
}
Comments
Post a Comment