Write a C program to Implement Circular Doubly Linked List and explain all its Operations with examples.
It is a kind of doubly linked list in which the node of the list is pointing to the head node and the previous pointer of the head node points to the last node. It makes doing many operations in constant time and sorting data is also possible.
Example:
Here is an example of the circular doubly linked list.
- Type Declaration of a Circular Doubly Linked List
- Implementation of Circular Doubly Linked List in C
- Traversing the Circular Doubly Linked List
- Insertion of a Node at the Beginning of the List
- Insertion of a Node at the End of the List
- Insertion of a New Node at the Given Position
- Deletion of a Node from the Beginning of the List
- Deletion of a Node from the End of the List
- Deletion of a Node from the Given Position
- Search a Node Data in the List
- Update a Node Data
- Sort the Circular Doubly Linked List
We have defined the type declaration of a node in the circular doubly linked list.
Node Syntax:
struct node { struct node* prev; int data; struct node* next; };
Every node contains the data and the reference of the next node and the previous node.
Here is source code of the C program to implement the circular doubly linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/* * C program to Implement the Circular Doubly Linked List */ #include<stdio.h> #include<stdlib.h> // structure of the node struct node { struct node* prev; int data; struct node* next; }; // global declaration of head node struct node* head = NULL; // function prototyping struct node* create(int); void insert_begin(int); void insert_end(int); void insert_mid(int, int); void delete_begin(); void delete_end(); void delete_mid(); int search(int); void update(int, int); void sort(); int list_size(); void display(); void display_reverse(struct node*); int get_data(); int get_position(); int main() { char user_active = 'Y'; int user_choice; int data, position; while(user_active == 'Y' || user_active == 'y') { printf("\n\n------ Circular Doubly Linked List -------\n"); printf("\n1. Insert a node at beginning"); printf("\n2. Insert a node at end"); printf("\n3. Insert a node at given position"); printf("\n\n4. Delete a node from beginning"); printf("\n5. Delete a node from end"); printf("\n6. Delete a node from given position"); printf("\n\n7. Print list from beginning"); printf("\n8. Print list from end"); printf("\n9. Search a node data"); printf("\n10. Update a node data"); printf("\n11. Sort the list"); printf("\n12. Exit"); printf("\n\n------------------------------\n"); printf("\nEnter your choice: "); scanf("%d", &user_choice); printf("\n------------------------------\n"); switch(user_choice) { case 1: printf("\nInserting a node at beginning"); data = get_data(); insert_begin(data); break; case 2: printf("\nInserting a node at end"); data = get_data(); insert_end(data); break; case 3: printf("\nInserting a node at the given position"); data = get_data(); position = get_position(); insert_mid(position, data); break; case 4: printf("\nDeleting a node from beginning\n"); delete_begin(); break; case 5: printf("\nDeleting a node from end\n"); delete_end(); break; case 6: printf("\nDelete a node from given position\n"); position = get_position(); delete_mid(position); break; case 7: printf("\nPrinting the list from beginning\n\n"); display(); break; case 8: printf("\nPrinting the list from end\n\n"); if (head == NULL) { printf("\n\tList is Empty!\n"); } else { display_reverse(head); } break; case 9: printf("\nSearching the node data"); data = get_data(); if (search(data) == 1) { printf("\n\tNode Found\n"); } else { printf("\n\tNode Not Found\n"); } break; case 10: printf("\nUpdating the node data"); data = get_data(); position = get_position(); update(position, data); break; case 11: sort(); printf("\nList was sorted\n"); break; case 12: printf("\nProgram was terminated\n\n"); return 0; default: printf("\n\tInvalid Choice\n"); } printf("\n...............................\n"); printf("\nDo you want to continue? (Y/N) : "); fflush(stdin); scanf(" %c", &user_active); } return 0; } // creates a new node struct node* create(int data) { struct node* new_node = (struct node*) malloc (sizeof(struct node)); if (new_node == NULL) { printf("\nMemory can't be allocated\n"); return NULL; } new_node->data = data; new_node->next = NULL; new_node->prev = NULL; return new_node; } // insert a new node at the beginning of the list void insert_begin(int data) { struct node* new_node = create(data); if (new_node) { // if list is empty if (head == NULL) { new_node->next = new_node; new_node->prev = new_node; head = new_node; return; } head->prev->next = new_node; new_node->prev = head->prev; new_node->next = head; head->prev = new_node; head = new_node; } } // inserts a new node at the end void insert_end(int data) { struct node* new_node = create(data); if (new_node) { if (head == NULL) { new_node->next = new_node; new_node->prev = new_node; head = new_node; return; } head->prev->next = new_node; new_node->prev = head->prev; new_node->next = head; head->prev = new_node; } } // inserts node at the given position void insert_mid(int position, int data) { // checking if the position is valid or not if (position <= 0) { printf("\nInvalid Position\n"); } else if (head == NULL && position > 1) { printf("\nInvalid Position\n"); } else if (head != NULL && position > list_size()) { printf("\nInvalid Position\n"); } else if (position == 1) { insert_begin(data); } else { struct node *new_node = create(data); if (new_node != NULL) { struct node *temp = head, *prev = NULL; int i = 1; // traverse the list to the given position while (++i <= position) { prev = temp; temp = temp->next; } // update the prev node to the new noe prev->next = new_node; // update the new node to the temp (position node) new_node->next = temp; } } } void delete_begin() { if (head == NULL) { printf("\nList is Empty\n"); return; } else if (head->next == head) { free(head); head = NULL; return; } struct node* temp = head; head->prev->next = head->next; head->next->prev = head->prev; head = head->next; free(temp); temp = NULL; } // deletes the node from the end of the list void delete_end() { if (head == NULL) { printf("\nList is Empty\n"); return; } else if (head->next == head) { free(head); head = NULL; return; } struct node* last_node = head->prev; last_node->prev->next = head; head->prev = last_node->prev; free(last_node); last_node = NULL; } // deletes the node from the given position void delete_mid(int position) { if (position <= 0) { printf("\n Invalid Position \n"); } else if (position > list_size()) { printf("\n Invalid position \n"); } else if (position == 1) { delete_begin(); } else if (position == list_size()) { delete_end(); } else { struct node *temp = head; struct node *prev = NULL; int i = 1; while (i < position) { prev = temp; temp = temp->next; i += 1; } prev->next = temp->next; temp->next->prev = prev; free(temp); temp = NULL; } } // search the node with the given key item int search(int key) { if (head == NULL) { printf("\n Not Found \n"); return 0; } struct node* temp = head; do { if (temp->data == key) { return 1; } temp = temp->next; } while (temp != head); return 0; } // updates the data of the given node position void update(int position, int new_value) { if (head == NULL) { printf("\n List is Empty \n"); return; } else if (position <= 0 || position > list_size()) { printf("\nInvalid position\n"); return; } struct node* temp = head; int i = 0; while (++i < position) { temp = temp->next; } temp->data = new_value; } // sorts the linked list data using insertion sort void sort() { if (head == NULL) { printf("\nList is Empty\n"); return; } struct node* temp1 = head; struct node* temp2 = head; int key = 0, value; do { temp2 = temp1->next; while(temp2 != head) { if (temp1->data > temp2->data) { value = temp1->data; temp1->data = temp2->data; temp2->data = value; } temp2 = temp2->next; } temp1 = temp1->next; }while (temp1->next != head); } // display the list void display() { if (head == NULL) { printf("\nList is empty!\n"); return; } struct node* temp = head; do { printf("%d ", temp->data); temp = temp->next; } while (temp != head); } // display the list from end to start void display_reverse(struct node* temp) { if (temp->next == head) { printf("%d ", temp->data); return; } display_reverse(temp->next); printf("%d ", temp->data); } // calculate the size of the list int list_size() { if (head == NULL) { return 0; } struct node* temp = head; int count = 0; do { count += 1; temp = temp->next; } while (temp != head); return count; } int get_data() { int data; printf("\n\nEnter Data: "); scanf("%d", &data); return data; } int get_position() { int position; printf("\n\nEnter Position: "); scanf("%d", &position); return position; }
In the given program of the circular doubly linked list, there are many functions that we need to understand and discuss the complexity of time and space.
In this article, we discuss the working of the primary functions below.
The traverse is the process of visiting the nodes once from the beginning to the end of the list. Below are the steps on how to traverse the list.
- Start iterating from beginning to end of the list using a temporary variable that stores the address of the first node.
- Iterate through the list until the head node comes again.
- Print the data that every node contains.
Time Complexity: O(n)
The time complexity of circular doubly linked list is O(n), here we are traversing the list from the beginning to the end. Here, n is the size of the list.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
When inserting a node at the beginning of this list, the following steps are necessary.
- Update the next pointer of the last node to the new node.
- Update the previous pointer of the new node to the last node.
- Update the previous pointer of the head node to the new node.
- Update the next pointer of the new node to the head node.
- Update the head pointer to the new node.
Example: Insert a new node with data 23 at the beginning of the list.
The circular doubly linked list is given below:
Step 1: Update the next pointer of the last node to the new node.
Step 2: Update the previous pointer of the new node to the last node.
Step 3: Update the previous pointer of the head node to the new node.
Step 4: Update the next pointer of the new node to the head node.
Step 5: Update the head pointer to the new node.
Time Complexity: O(1)
Because no traversal takes place to the insertion of a node at the beginning, thus time complexity of this method is constant.
Space Complexity: O(1)
A constant amount of space is taken to insert the new node at the beginning.
In this case, we are inserting the nodes from the beginning of the doubly singly linked list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 1 ------------------------------ Inserting a node at beginning Enter Data: 67 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 1 ------------------------------ Inserting a node at beginning Enter Data: 88 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 1 ------------------------------ Inserting a node at beginning Enter Data: 23 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 Printing the list from beginning 23 88 67 ............................... Do you want to continue? (Y/N) : n
We have to follow the given steps to insert a new node at the end of the list.
- Update the next pointer of the last node to the new node.
- Update the previous pointer of the new node to the last node.
- Update the previous pointer of the head node to the new node.
- Update the next pointer of the new node to the head node.
Example: Insert a new node with data 32 at the end of the list. Following is the given circular doubly linked list.
Step 1: Update the next pointer of the last node to the new node.
Step 2: Update the previous pointer of the new node to the last node.
Step 3: Update the previous pointer of the head node to the new node.
Step 4: Update the next pointer of the new node to the head node.
Time Complexity: O(1)
There is no need to traverse the list so time is constant in this operation is O(1).
Space Complexity: O(1)
Since we are using only temporary variables to perform this operation, space is constant i.e O(1).
In this case, we are inserting the nodes from the end of the circular singly linked list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 Printing the list from beginning 23 88 67 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 2 ------------------------------ Inserting a node at end Enter Data: 32 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 23 88 67 32 ............................... Do you want to continue? (Y/N) : n
Inserting a new node at the given position needs to follow the given steps:
- Traverse the list to the given position K.
- Update the next pointer of the K-1th node to the new node.
- Update the next pointer of the new node to the Kth node.
- Update the prev of the Kth (temp) node to the new node.
- Update the next pointer of the new node to the Kth(temp) node.
Example: Insert a new node with data 33 at position 3.
Step 1: Traverse the list to the given position K = 3. (1-based index)
Step 2: Update the next pointer of the K-1th node to the new node.
Step 3: Update the prev pointer of the new node to the K-1th node.
Step 4: Update the prev of the Kth (temp) node to the new node.
Step 5: Update the next pointer of the new node to the Kth(temp) node.
Time Complexity: O(n)
There is a need for traversal to reach the given position. In the worst case, we need to traverse the entire list so that the time complexity is linear that is O(n).
Space Complexity: O(1)
Only the temporary variables are taken for this operation so space is constant i.e O(1).
In this case, we are inserting the nodes at the particular position in the list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 23 88 67 32 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 3 ------------------------------ Inserting a node at the given position Enter Data: 33 Enter Position: 3 * Node with data 33 was inserted ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 23 88 33 67 32 ............................... Do you want to continue? (Y/N) : n
Deleting a node from the beginning of the list needs to follow the given steps:
- Update the next pointer of the last node to the next node of the head node.
- Update the prev pointer of the next node of the head node to the last node.
- Move the head to its next node.
- Free the last head node.
Example: Deleting a node with data 88 from the beginning of the list.
Step 1: Update the next pointer of the last node to the next node of the head node.
Step 2: Update the prev pointer of the next node of the head node to the last node.
Step 3: Move the head to its next node.
Step 4: Free the last head node.
Time Complexity: O(1)
To change the last node reference we do not have to traverse the entire list so that the time complexity is constant.
Space Complexity: O(1)
Space is constant due to temporary variables being taken.
In this case, we are deleting the nodes from the beginning of the circular doubly linked list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 23 88 33 67 32 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 4 ------------------------------ Deleting a node from beginning * Node with data 23 was Deleted .............................. Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 88 33 67 32 ............................... Do you want to continue? (Y/N) : y
Deletion of a node from the end of the circular doubly linked list takes the following steps:
- Update the next pointer of the N-1th node to the head node.
- Update the prev pointer of the head node to the N-1th node.
- Free the Nth node.
Example: Deleting the last node having data 92.
Step 1: Update the next pointer of the N-1th node to the head node.
Step 2: Update the prev pointer of the head node to the N-1th node.
Step 3: Free the Nth node.
Time Complexity: O(1)
It takes a constant amount of time to perform this operation.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
In this case, we are deleting the nodes from the end of the circular doubly linked list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 88 33 67 32 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 5 ------------------------------ Deleting a node from end * Node with data 32 was Deleted ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 88 33 67 ............................... Do you want to continue? (Y/N) : n
To delete a node from the given position, we have to follow the given steps:
- Traverse the list up to the given position K.
- Update the next pointer of the K-1th node to the K+1th node.
- Update the previous pointer of the K+1th node to the K-1th node.
- Free the Kth node
Example: Deleting the 2nd node with data 67 of the given list.
Step 1: Traverse the list up to the given position K.
Step 2: Update the next pointer of the K-1th node to the K+1th node.
Step 3: Update the prev pointer of the K+1th node to the K-1th node.
Step 4: Free the Kth node.
Time Complexity: O(n)
Traversing is needed to reach the given position so the complexity becomes linearly dependent on the size of the list in the worst case.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
In this case, we are deleting the node from the particular position of the list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 88 33 67 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 6 ------------------------------ Enter Position: 1 * Node with data 88 was Deleted ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 33 67 ............................... Do you want to continue? (Y/N) : n
Searching is the process to find a value in the linked list. We have to follow the given steps to search for the value in the list.
- Traverse from start to end of the list.
- Match the node data with the given key.
Time Complexity: O(n)
Since we are traversing the list from beginning to end, the complexity depends on the size of the list which is n.
Space Complexity: O(1)
Finding the key in the list takes a constant amount of space.
In this case, we are searching for a node in the list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 33 67 45 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 9 ------------------------------ Searching the node data Enter Data: 67 Found data at 2 position ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 9 ------------------------------ Searching the node data Enter Data: 18 Data not Found ............................... Do you want to continue? (Y/N) : n
Updation is the process to change the current node value with the new value. It needs to follow the given steps:
- Traverse the list up to the given position.
- Update the value of the node with the new given value.
Time Complexity: O(n)
In the worst case, the complexity to update the node takes linear time which is the size of the list.
Space Complexity: O(1)
Since we are using only temporary variables, space is constant.
In this case, we are updating a node data at a particular position.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 33 67 45 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 10 ------------------------------ Updating the node data Entert Data: 15 Enter Position: 1 Updated node data is 15 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 15 33 67 45 ............................... Do you want to continue? (Y/N) : n
Sorting refers to arranging data in a particular format. Here we are using the insertion sort technique to sort the list.
Time Complexity: O(n2)
The complexity of the insertion sort in the worst case is O(n2).
Space Complexity: O(1)
Only temporary variables are taken for this operation.
In this case, we are sorting the list.
------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 33 67 45 ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 11 ------------------------------ List was sorted ............................... Do you want to continue? (Y/N) : y ------ Circular Doubly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Sort the list 12. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 33 45 67 ............................... Do you want to continue? (Y/N) : n
To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.
- Practice Design & Analysis of Algorithms MCQ
- Practice Programming MCQs
- Check Programming Books
- Check Data Structure Books
- Check Computer Science Books