In the circular linked list the last node of the list contains the address of the first node and forms a circular chain.

screenshot_40

Basic operations

1. Insert – Inserts a new element at the end of the list.

2. Delete – Deletes any node from the list.

3. Find – Finds any node in the list.

4. Print – Prints the list.

Algorithm:

The node of a linked list is a structure with fields data (which stored the value of the node) and

*next (which is a pointer of type node that stores the address of the next node).

Two nodes *start (which always points to the first node of the linked list) and *temp (which is

used to point to the last node of the linked list) are initialized. Initially temp = start and temp->next = start.

Here, we take the first node as a dummy node. The first node does not contain data,

but it used because to avoid handling special cases in insert and delete functions.

Function

〈1〉.Insert – This function takes the start node and data to be inserted as arguments. New node

      is inserted at the end so, iterate through the list till we encounter the last node. Then,

      allocate memory for the new node and put data in it. Lastly, store the address of the first

      node (start) in the next field of the new node.

〈2〉. Delete – This function takes the start node (as pointer) and data to be deleted as

       arguments. Firstly, go to the node for which the node next to it has to be deleted,

       If that node points to NULL (i.e. pointer>next=NULL) then the element to be

       deleted is not present in the list.

       Else, now pointer points to a node and the node next to it has to be removed,

       declare a temporary node (temp) which points to the node which has to be

       removed. Store the address of the node next to the temporary node in the next

       field of the node pointer (pointer->next = temp->next). Thus, by breaking the link

      we removed the node which is next to the pointer (which is also temp). Because

       we deleted the node, we no longer require the memory used for it, free() will

      de allocate the memory.

〈3〉. Find – This function takes the start node (as pointer) and data value of the node (key)

       to be found as arguments. A pointer start of type node is declared, which points to the

       head node of the list (node *start = pointer). First node is dummy node so, start with the

        second node. Iterate through the entire linked list and search for the key.

        Until next field of the pointer is equal to start, check if pointer->data = key. If it is

        then the key is found else, move to the next node and search (pointer = pointer ->next). If key is not found

        return 0, else return 1.

〈4〉. Print – function takes the start node (as start) and the next node (as pointer) as arguments.

       If pointer = start, then there is no element in the list. Else, print the data value of the node

       (pointer->data) and move to the next node by recursively calling the print function with 

        pointer->next sent as an argument.

Program

#include
#include
typedef struct Node
{
        int data;
        struct Node *next;
}node;
void insert(node *pointer, int data)
{
        node *start = pointer;
        /* Iterate through the list till we encounter the last node.*/
        while(pointer->next!=start)
        {
                pointer = pointer -> next;
        }
        /* Allocate memory for the new node and put data in it.*/
        pointer->next = (node *)malloc(sizeof(node));
        pointer = pointer->next;
        pointer->data = data;
        pointer->next = start;
}
int find(node *pointer, int key)
{
        node *start = pointer;
        pointer =  pointer -> next; //First node is dummy node.
        /* Iterate through the entire linked list and search for the key. */
        while(pointer!=start)
        {
                if(pointer->data == key) //key is found.
                {
                        return 1;
                }
                pointer = pointer -> next;//Search in the next node.
        }
        /*Key is not found */
        return 0;
}
void delete(node *pointer, int data)
{
        node *start = pointer;
        /* Go to the node for which the node next to it has to be deleted */
        while(pointer->next!=start && (pointer->next)->data != data)
        {
                pointer = pointer -> next;
        }
        if(pointer->next==start)
        {
                printf(“Element %d is not present in the listn”,data);
                return;
        }
        /* Now pointer points to a node and the node next to it has to be removed */
        node *temp;
        temp = pointer -> next;
        /*temp points to the node which has to be removed*/
        pointer->next = temp->next;
        /*We removed the node which is next to the pointer (which is also temp) */
        free(temp);
        /* Beacuse we deleted the node, we no longer require the memory used for it .
           free() will deallocate the memory.
         */
        return;
}
void print(node *start,node *pointer)
{
        if(pointer==start)
        {
                return;
        }
        printf(“%d “,pointer->data);
        print(start,pointer->next);
}
int main()
{
        /* start always points to the first node of the linked list.
           temp is used to point to the last node of the linked list.*/
        node *start,*temp;
        start = (node *)malloc(sizeof(node));
        temp = start;
        temp -> next = start;
        /* Here in this code, we take the first node as a dummy node.
           The first node does not contain data, but it used because to avoid handling special cases
           in insert and delete functions.
         */
        printf(“1. Insertn”);
        printf(“2. Deleten”);
        printf(“3. Printn”);
        printf(“4. Findn”);
        while(1)
        {
                int query;
                scanf(“%d”,&query);
                if(query==1)
                {
                        int data;
                        scanf(“%d”,&data);
                        insert(start,data);
                }
                else if(query==2)
                {
                        int data;
                        scanf(“%d”,&data);
                        delete(start,data);
                }
                else if(query==3)
                {
                        printf(“The list is “);
                        print(start,start->next);
                        printf(“n”);
                }
                else if(query==4)
                {
                        int data;
                        scanf(“%d”,&data);
                        int status = find(start,data);
                        if(status)
                        {
                                printf(“Element Foundn”);
                        }
                        else
                        {
                                printf(“Element Not Foundn”);

                        }
                }
        }

}