Circular linked list

Here we will discuss how circular linked list can be implemented using singly linked list.Circular linked list is a linked list in which the last node points back to the head node.

A node comprises of the following fields.

Data field where data is stored.

Next pointer : This pointer points to the next node of the list.

head is a pointer pointing to the 1st node. 

next pointer of the last node points back to the head node.

Lets say we have an organization in which some employees work and you have to store their details.You should also be able to add,delete and modify employee details.For better understanding I have taken only employee id in employee details.Here we will treat a employee as node.

Building a circular linked list

1.  Declare a node structure

typedef struct node
{
        int id;
        struct node* next;                       //for storing address of next node
}node;

Note:Members of structure can be accessed via pointer using ->

2.  Create a linked list

node* create()
{
    node* head;
    head=(node*)malloc(sizeof(node));            /*allocating memory to node 
                                                   and head is pointing to it  */

    printf("\nEnter employee id ");
    scanf("%d",&head->id);

    head->next=head;
    return head;
}   

3.  Append a node to a linked list

node* append(node* head)
{
    node* curr = (node*)malloc(sizeof(node));  //allocate memory for current node

    node* prev = head;

    printf("\nEnter employee id ");
    scanf("%d",&curr->id);

    while(prev->next!=head)                    //traverse the list and go to the last node
        prev = prev->next;

    prev->next = curr;                          /*establish the link between last node
                                                  (pointed by prev) and curr node   */

    curr->next = head;

    return head;
}         

4.  Modify a node of a linked list

node* modify(node* head)
{
    node* curr=head;
    int eid,found=0;

    printf("\nEnter Eid of employee whose data is to be modified ");
    scanf("%d",&eid);

    do                                         //traverse list in search of eid
    {
           if(curr->id==eid)
           {
              found = 1;
              break;
           }
           else
              curr=curr->next;
    }while(curr!=head);

    if(found == 1)                            //eid is found
    {
            printf("\nEnter employee id ");
            scanf("%d",&curr->id);
    }
    else
            printf("\nEmployee id not found");

    return head;
}

5.  Delete node from a linked list

node* del(node* head)
{
    node *prev,*curr=head,*last;
    int eid;

    printf("\nEnter employee id to be deleted ");
    scanf("%d",&eid);

    if(curr==NULL)
           return NULL;

    else if(curr->id==eid && curr->next==curr)          //only 1 node
    {
           free(curr);
           return NULL;
    }

    else if(curr->id==eid && curr->next!=head)          //1st node
    {
           head=head->next;

           last = head;                                //go to last node
           do                                               
           {
                 last=last->next;
           }while(last->next!=curr);

           last->next=head;

           free(curr);
           return head;
    }


    else
    {
           do                                           //search eid
           {
               if(curr->id==eid)
                    break;
               else
               {
                    prev=curr;
                    curr=curr->next;
               } 
            }while(curr!=head);

            if(curr!=head)                              //if eid found
            {
                   //establish the link between prev & node ahead of curr
                   prev->next=curr->next;

                   free(curr);
            }
            else
                   printf("\nEmployee id not found");

            return head;
       }
}

Here curr  = points to the node to be deleted

last = points to the last node

Suppose we have

We have to delete node pointed by curr i.e node 1.So we advance head.But next pointer of last node (node 3) is pointing to node 1.But as node 2 is new head we make next pointer of node 3 point to it.

Diagram after deletion of node 1.

6.  Display linked list

void display(node* head)
{
    node* curr=head;

    if(curr==NULL)
           printf("\nList is empty");
    else
    {
            printf("\n");

            do
            {
                 printf("%d---",curr->id);
                 curr=curr->next;
            }while(curr!=head);

    }
}

Complete code with output