C Program to Implement Circular Doubly Linked List

Problem Description

Write a C program to Implement Circular Doubly Linked List and explain all its Operations with examples.

What is a Circular Doubly Linked List in C?

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.

Circular doubly linked list example

Circular Doubly Linked List and its Operations in C:

Type Declaration of a Circular Doubly Linked List in C

We have defined the type declaration of a node in the circular doubly linked list.

Singly Linked List Node Structure

advertisement
advertisement

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Circular Doubly Linked List Implementation in C

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;
}
Program Explanation:

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.

advertisement
Traversing the Circular Doubly Linked List

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.

  1. Start iterating from beginning to end of the list using a temporary variable that stores the address of the first node.
  2. Iterate through the list until the head node comes again.
  3. 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.

Insert a Node at Beginning of the List

When inserting a node at the beginning of this list, the following steps are necessary.

advertisement
  1. Update the next pointer of the last node to the new node.
  2. Update the previous pointer of the new node to the last node.
  3. Update the previous pointer of the head node to the new node.
  4. Update the next pointer of the new node to the head node.
  5. 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:

Circular doubly linked list node insertion at beginning example

Step 1: Update the next pointer of the last node to the new node.

Circular doubly linked list node insertion at beginning of the list

Step 2: Update the previous pointer of the new node to the last node.

Circular doubly linked list node insertion at beginning of the list

Step 3: Update the previous pointer of the head node to the new node.

Circular doubly linked list node insertion at beginning of the list

Step 4: Update the next pointer of the new node to the head node.

Circular doubly linked list node insertion at beginning of the list

Step 5: Update the head pointer to the new node.

Circular doubly linked list node insertion at beginning of the list

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.

Run Time Testcases

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

Insert a Node at the End

We have to follow the given steps to insert a new node at the end of the list.

  1. Update the next pointer of the last node to the new node.
  2. Update the previous pointer of the new node to the last node.
  3. Update the previous pointer of the head node to the new node.
  4. 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.

Circular doubly linked list node insertion at end example

Step 1: Update the next pointer of the last node to the new node.

Circular doubly linked list node insertion at end of the list

Step 2: Update the previous pointer of the new node to the last node.

Circular doubly linked list node insertion at end of the list

Step 3: Update the previous pointer of the head node to the new node.

Circular doubly linked list node insertion at end of the list

Step 4: Update the next pointer of the new node to the head node.

Circular doubly linked list node insertion at end of the list

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).

Run Time Testcases

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

Insert a Node at a Given Position

Inserting a new node at the given position needs to follow the given steps:

  1. Traverse the list to the given position K.
  2. Update the next pointer of the K-1th node to the new node.
  3. Update the next pointer of the new node to the Kth node.
  4. Update the prev of the Kth (temp) node to the new node.
  5. 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)

Circular doubly linked list - Insert a node at a given position

Step 2: Update the next pointer of the K-1th node to the new node.

Circular doubly linked list - Insert a node at a given position

Step 3: Update the prev pointer of the new node to the K-1th node.

Circular doubly linked list - Insert a node at a given position

Step 4: Update the prev of the Kth (temp) node to the new node.

Circular doubly linked list - Insert a node at a given position

Step 5: Update the next pointer of the new node to the Kth(temp) node.

Circular doubly linked list - Insert a node at a given position

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).

Run Time Testcases

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

Delete a Node from the Beginning

Deleting a node from the beginning of the list needs to follow the given steps:

  1. Update the next pointer of the last node to the next node of the head node.
  2. Update the prev pointer of the next node of the head node to the last node.
  3. Move the head to its next node.
  4. 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.

Circular Doubly Linked List - Delete a Node from the Beginning of the List

Step 2: Update the prev pointer of the next node of the head node to the last node.

Circular Doubly Linked List - Delete a Node from the Beginning of the List

Step 3: Move the head to its next node.

Circular Doubly Linked List - Delete a Node from the Beginning of the List

Step 4: Free the last head node.

Circular Doubly Linked List - Delete a Node from the Beginning of the List

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.

Run Time Testcases

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

Delete a Node from the End

Deletion of a node from the end of the circular doubly linked list takes the following steps:

  1. Update the next pointer of the N-1th node to the head node.
  2. Update the prev pointer of the head node to the N-1th node.
  3. 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.

Circular Doubly Linked List - Delete a Node from the End of the List

Step 2: Update the prev pointer of the head node to the N-1th node.

Circular Doubly Linked List - Delete a Node from the End of the List

Step 3: Free the Nth node.

Circular Doubly Linked List - Delete a Node from the End of the List

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.

Run Time Testcases

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

Delete a Node from the Given Position

To delete a node from the given position, we have to follow the given steps:

  1. Traverse the list up to the given position K.
  2. Update the next pointer of the K-1th node to the K+1th node.
  3. Update the previous pointer of the K+1th node to the K-1th node.
  4. 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.

Circular Doubly Linked List - Delete a Node from the position of the List

Step 2: Update the next pointer of the K-1th node to the K+1th node.

Circular Doubly Linked List - Delete a Node from the position of the List

Step 3: Update the prev pointer of the K+1th node to the K-1th node.

Circular Doubly Linked List - Delete a Node from the position of the List

Step 4: Free the Kth node.

Circular Doubly Linked List - Delete a Node from the position of the List

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.

Run Time Testcases

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

Search a Node Data in the List

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.

  1. Traverse from start to end of the list.
  2. 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.

Run Time Testcases

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

Update the Node Data

Updation is the process to change the current node value with the new value. It needs to follow the given steps:

  1. Traverse the list up to the given position.
  2. 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.

Run Time Testcases

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

Sort the Circular Doubly Linked List

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.

Run Time Testcases

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”.

If you find any mistake above, kindly email to [email protected]

Related Posts:

advertisement

Recommended Articles:

  1. C Program to Implement Xor Linked List
  2. C++ Program to Implement Circular Doubly Linked List
  3. C Program to Find the Largest Element in a Doubly Linked List
  4. C Program to Convert Binary Tree to Circular Doubly Linked List
  5. C Program to Implement Doubly Linked List using Singly Linked List
  6. C++ Program to Implement Sorted Doubly Linked List
  7. C++ Program to Implement Sorted Circularly Doubly Linked List
  8. C Program to Convert Singly Linked List to Circular List
  9. C program to Swap Two Nodes in a Circular Linked List
  10. Python Program to Implement Circular Doubly Linked List
advertisement
Additional Resources:
Popular Pages:
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.