Circular Singly Linked List in C

«
»
Program Description

Write a program to implement Circular Singly Linked List in C.

What is a Circular Singly Linked List?

Circular Linked List is a kind of singly linked list in which the last node of a list is pointing to the first node. Let us understand it by the following example.

Circular Singly Linked List Example

In a circular linked list, every node points to the next node. The Last node of the last point back to the head node.

Circular Singly Linked List and its Operations in C:

Type Declaration of a Linked List

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

Singly Linked List Node Structure

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Node Syntax:

struct node
{
     int data;
     struct node* next;
};

Every node contains the data and the reference of the next node.

Circular Singly Linked List Implementation

Here is source code of the C program to implement the circular singly 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 Singly Linked List
 */
 
#include <stdio.h>
#include <stdlib.h>
 
struct node
{
    int data;
    struct node *next;
};
 
struct node *head;
 
// function prototyping
struct node *create(int);
void insert_at_begin(int);
void insert_at_end(int);
void insert_at_position(int, int);
void delete_at_begin();
void delete_at_end();
void delete_at_position(int);
void search(int);
void update(int, int);
void print_list();
void print_list_reverse();
int size_of_list();
int getData();
int getPosition();
 
int main()
{
    char user_active = 'Y';
    int user_choice;
    int data, position;
 
    while(user_active == 'Y' || user_active == 'y')
    {
 
        printf("\n\n------ Circular Singly 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. 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 = getData();
                insert_at_begin(data);
                break;
 
            case 2:
                printf("\nInserting a node at end");
                data = getData();
                insert_at_end(data);
                break;
 
            case 3: 
                printf("\nInserting a node at the given position");
                data = getData();
                position = getPosition();
                insert_at_position(data, position);
                break;
 
            case 4: 
                printf("\nDeleting a node from beginning\n");
                delete_at_begin();
                break;
 
            case 5: 
                printf("\nDeleting a node from end\n");
                delete_at_end();
                break;
 
            case 6: 
                printf("\nDelete a node from given position\n");
                position = getPosition();
                delete_at_position(position);
                break;
 
            case 7: 
                printf("\nPrinting the list from beginning\n\n");
                print_list();
                break;
 
            case 8: 
                printf("\nPrinting the list from end\n\n");
                if (head == NULL) {
                    printf("\n\tList is Empty!\n");
                } else {
                    print_list_reverse(head);
                }
                break;
 
            case 9:
                printf("\nSearching the node data");
                data = getData();
                search(data);
                break;
 
            case 10:
                printf("\nUpdating the node data");
                data = getData();
                position = getPosition();
                update(position, data);
                break;
 
            case 11:
                printf("\nProgram was terminated\n\n");
                return 0;
 
            default:
                printf("\n\t Invalid Choice\n");
        }
 
        printf("\n...............................\n");
        printf("\nDo you want to continue? (Y/N) : ");
        fflush(stdin);
        scanf(" %c", &user_active);
    }
 
    return 0;
}
 
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;
 
    return new_node;
}
 
// function to insert a new node at the beginning of the list
void insert_at_begin(int data)
{
    struct node *new_node = create(data);
 
    if (new_node != NULL)
    {
        struct node *last = head;
 
        // if the list is empty
        if (head == NULL)
        {
            head = new_node;
            new_node->next = head;
            return;
        }
 
        // traverse to the end node
        while (last->next != head)
        {
            last = last->next;
        }
 
        // update  the last node to the new node
        last->next = new_node;
 
        // update the next pointer of the new node to the head node
        new_node->next = head;
 
        // update the head of the list to new node
        head = new_node;
    }
}
 
// function to insert a new node at the end of the list
void insert_at_end(int data)
{
    struct node *new_node = create(data);
 
    if (new_node != NULL)
    {
 
        // if the list is empty
        if (head == NULL)
        {
            head = new_node;
            new_node->next = head;
            return;
        }
 
        struct node *last = head;
 
        // traverse to the end node
        while (last->next != head)
        {
            last = last->next;
        }
 
        // update  the last node to the new node
        last->next = new_node;
 
        // update the next pointer of the new node to the head node
        new_node->next = head;
    }
}
 
// function to insert a new node at the given position
void insert_at_position(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 > size_of_list())
    {
        printf("\nInvalid Position\n");
    }
    else if (position == 1)
    {
        insert_at_begin(data);
    }
    else
    {
        struct node *new_node = create(data);
 
        if (new_node != NULL)
        {
            struct node *temp = head, *prev = NULL;
            // Since, temp is already pointing to first node 
            // then count will be start at second node
            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;
        }
    }
}
 
// function to delete a node from the beginning of the list
void delete_at_begin()
{
    // check where the list is empty or not
    if (head == NULL)
    {
        printf("\n List is Empty! \n");
        return;
    }
 
    // traverse to the end of the list
    struct node *last = head;
    struct node *temp = head;
 
    // if only one node in the list
    if (last->next == head)
    {
        free(last);
        head = NULL;
        return;
    }
 
    // traverse to the last node
    while (last->next != head)
    {
        last = last->next;
    }
 
    head = head->next;
    last->next = head;
 
    free(temp);
    temp = NULL;
}
 
// function to delete a node from the end of the list
void delete_at_end()
{
    // check where the list is empty or not
    if (head == NULL)
    {
        printf("\n List is Empty! \n");
        return;
    }
 
    // traverse to the end of the list
    struct node *prev = head;
    struct node *temp = head->next;
 
    // if only one node in the list
    if (prev->next == head)
    {
        free(prev);
        head = NULL;
        return;
    }
 
    while (temp->next != head)
    {
        prev = temp;
        temp = temp->next;
    }
 
    prev->next = head;
 
    free(temp);
    temp = NULL;
}
 
// function to delete a node from the given position
void delete_at_position(int position)
{
    if (position <= 0)
    {
        printf("\n Invalid Position \n");
    }
    else if (position > size_of_list())
    {
        printf("\n Invalid position \n");
    }
    else if (position == 1)
    {
        delete_at_begin();
    }
    else if (position == size_of_list())
    {
        delete_at_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;
        free(temp);
        temp = NULL;
    }
}
 
// print the node values
void print_list()
{
    struct node *temp = head;
 
    if (head == NULL)
    {
        printf("\n List is Empty! \n");
        return;
    }
 
    printf("\n");
    do
    {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
 
    printf("\n");
}
 
// print the node values recursively
void print_list_reverse(struct node* temp)
{
    if (temp->next == head)
    {
        printf("%d ", temp->data);
        return;
    }
    print_list_reverse(temp->next);
    printf("%d ", temp->data);
}
 
// search a data into the list
void search(int key)
{
    struct node* temp = head;
 
    do
    {
        if (temp->data == key)
        {
            printf("\n\t Data Found\n");
            return;
        }
        temp = temp->next;
    }while (temp->next != head);
    printf("\n\tData not Found\n");
}
 
// function to update a node
void update(int position, int new_data)
{
    if (position <= 0 || position > size_of_list())
    {
        printf("\n Invalid position\n");
        return;
    } 
 
    struct node* temp = head;
    int i = 0;
 
    while (i <= position)
    {
        temp = temp->next;
        i += 1;
    }
 
    temp->data = new_data;
}
 
// function to calculate the size of the list
int size_of_list()
{
    if (head == NULL)
    {
        return 0;
    }
 
    struct node *temp = head;
    int count = 1;
 
    while (temp->next != head)
    {
        count += 1;
        temp = temp->next;
    }
    return count;
}
 
int getData()
{
    int data;
    printf("\n\nEnter Data: ");
    scanf("%d", &data);
 
    return data;
}
 
int getPosition()
{
    int pos;
    printf("\n\nEnter Position: ");
    scanf("%d", &pos);
 
    return pos;
}
Program Explanation:

Some functions are performing the different operations on the list. We are discussing these functions and understanding how they are working.

Traversing the Circular Singly Linked List in C

Traversing is the process of visiting the nodes one time from start to end of the list. Following are the steps required to traverse the list.

advertisement
  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 singly 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

Inserting a new node in the list increases the size of the list by one. These are the following steps to insert the new node at the beginning of the list:

  1. Traverse the list to the last node.
  2. Update the next pointer of the last node to the new node.
  3. Update the next pointer of the new node to the head node.
  4. Update the head node to the new node.

Example: Insert a new node with data 99 at the beginning of the list.

advertisement

Step 1: Traverse the list to the last node.

Circular singly linked list Node Insertion - Traverse the list to the last node

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

Circular singly linked list Node Insertion - Update the next pointer of the last node to the new node

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

Circular singly linked list Node Insertion - Update the next pointer of the new node to the head node

Step 4: Update the head node to the new node.

Circular singly linked list Node Insertion - Update the head node to the new node

Time Complexity: O(n)
The time complexity of circular singly linked list in C is O(n), since we are traversing from the beginning to end, time depends on the size of the list.

Space Complexity: O(1)
Constant amount of space is taken to insert the new node at the beginning. So, the space complexity is constant i.e. O(1).

Run Time Testcases

In this case, we are inserting the nodes from the beginning of the circular singly linked list.

------ Circular Singly 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. Exit
 
------------------------------
Enter your choice: 1
------------------------------
 
Inserting a node at beginning
 
Enter Data: 90
...............................
 
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
 
------------------------------
Enter your choice: 1
------------------------------
 
Inserting a node at beginning
 
Enter Data: 78
...............................
 
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
 
------------------------------
Enter your choice: 1
------------------------------
 
Inserting a node at beginning
 
Enter Data: 99
...............................
 
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
 
------------------------------
Enter your choice: 7
------------------------------
 
Printing the list from beginning
 
99 78 90 
...............................
 
Do you want to continue? (Y/N) : n

Insert a Node at the End

The size of the list increased by one on the insertion of a new node. We have to follow the given steps to insert a new node at the end of the list.

  1. Traverse the list to the last node.
  2. Update the next pointer of the last node to the new node.
  3. Update the next pointer of the new node to the head node.

Example: Insert a new node with data 35 at the end of the list.

Step 1: Traverse the list to the last node.

Circular singly linked list node insertion at end

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

Circular singly linked list node insertion at end

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

Circular singly linked list node insertion at end

Time Complexity: O(n)
Since we need to go to the last node by traversing the list. Time is linearly dependent on the size of the list which is n.

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 inserting the nodes from the end of the circular singly linked list.

------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
99 78 90
...............................
Do you want to continue? (Y/N) : Y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 2
------------------------------
Inserting a node at end
 
Enter Data: 35
...............................
 
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
99 78 90 35 
...............................
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.

Example: Insert a new node with data 35 at position 2.

Step 1: Traverse the list to the given position K = 3. (1-based index)

Circular singly 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 singly linked list - Insert a node at a given position

Step 3: Update the next pointer of the new node to the Kth node.

Circular singly 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.

Space Complexity: O(1)
Only the temporary variables are taken for this operation so space is constant.

Run Time Testcases

In this case, we are inserting the nodes at the particular position in the list.

------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
99 78 90 35 
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 3
------------------------------
Inserting a node at the given position
 
Enter Data: 65
 
Enter Position: 2
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
99 12 78 90 35 
...............................
Do you want to continue? (Y/N) : n

Delete a Node from the Beginning

Deletion of a node reduces the size of the list by one. Deletion requires the following steps:

  1. Traverse the list to the end node.
  2. Update the next pointer of the last node to the next of the head node.
  3. Update the head to the next of the head node.
  4. Free the last head node.

Example: Deleting a node with data 56 from the beginning of the list.

Step 1: Traverse the list to the node.

Circular singly linked list - Delete a Node from the Beginning

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

Circular singly linked list - Delete a Node from the Beginning

Step 3: Update the head to the next of the head node.

Circular singly linked list - Delete a Node from the Beginning

Step 4: Free the last head node.

Circular singly linked list - Delete a Node from the Beginning

Time Complexity: O(n)
To change the last node reference we have to traverse the list and it makes this operation linearly dependent on the size of the list.

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 singly linked list.

------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
99 12 78 90 35 
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 4
------------------------------
Deleting a node from beginning
 
* Node with data 99 was Deleted
..............................
 
Do you want to continue? (Y/N) : y
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
12 78 90 35 
...............................
Do you want to continue? (Y/N) : n

Delete a Node from the End

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

  1. Traverse the list to the N-1th node, where N is the number of nodes.
  2. Update the next pointer of the N-1th node to the head node.
  3. Free the Nth node.

Example: Deleting the last node having data 35.

Step 1: Traverse the list to the N-1th node, where N is the number of nodes.

Circular Singly Linked List - Delete a Node from the End

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

Circular Singly Linked List - Delete a Node from the End

Step 3: Free the Nth node.

Circular Singly Linked List - Delete a Node from the End

Time Complexity: O(n)
Traversing is needed to reach the last node so the complexity becomes linearly dependent on the size of the list.

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 singly linked list.

------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
12 78 90 35 
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 5
------------------------------
Deleting a node from end
 
* Node with data 35 was Deleted
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
12 78 90
...............................
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 upto the given position K.
  2. Update the next pointer of the K-1th node to the K+1th node.
  3. Free the Kth node.

Example: Deleting the 3rd node of the given list.

Step 1: Traverse the list upto the given position.

Circular Singly Linked List - Delete a Node from the Given Position

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

Circular Singly Linked List - Delete a Node from the Given Position

Step 3: Free the temp node.

Circular Singly Linked List - Delete a Node from the Given Position

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 Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
12 78 90
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 6
------------------------------
Enter Position: 1
 
* Node with data 12 was Deleted
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
78 90
...............................
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 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)
It takes a constant amount of space to find the key in the list.

Run Time Testcases

In this case, we are searching for a node in the list.

------ Circular Singly 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. Exit
------------------------------
Enter your choice: 8
------------------------------
Printing the list from end
 
90 78 12
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 9
------------------------------
Searching the node data
 
Enter Data: 78
 
Found data at 2 position
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 9
------------------------------
Searching the node data
 
Enter Data: 74
 
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 upto 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 Singly 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. Exit
------------------------------
Enter your choice: 8
------------------------------
Printing the list from end
90 78 12
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 10
------------------------------
Updating the node data
 
Entert Data: 40
 
Enter Position: 1
 
Updated node data is 40
...............................
Do you want to continue? (Y/N) : y
 
------ Circular Singly 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. Exit
------------------------------
Enter your choice: 7
------------------------------
Printing the list from end
40 12 78 90
...............................
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”.

advertisement
advertisement
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 & technical discussions at Telegram SanfoundryClasses.