Circular Linked list

Circular linked list is a list where all nodes are connected to form a circle. In circular linked list, there is no NULL node at the end. A circular linked list can be a singly circular linked list or doubly linked list.

In the above figure, the node A is a head node and all the  node is linked and there is no Null node like Singly Linked List.

Implementation

To implement a Circular Singly Linked List, we take an external pointer that points to the last node of the list. If we have a pointer, pointing to the last node of the list, then last-> next will be the first node.

The pointer Last points to the node Q and last->next points to the node P.

Why we have taken the pointer that points to the last node of the list instead of the first node?

While inserting the new node to the Circular Linked list in the beginning of the list (head), we need to traverse the whole list, if it is pointing the head node. And also for inserting the node at the end, the whole list has to be traversed. Hence, the complexity is high as we traverse the whole list for inserting the node at the beginning and at the end. For better solution, we always point the pointer to the last node of the list. Hence insertion at the beginning and at the end, always take constant time irrespective of the length of the circular list.

Insertion

The node can be inserted in Circular linked list in three ways such as:

• Insertion in an empty list
• Insertion at the beginning of the list
• Insertion at the end of the list
• Insertion in between the nodes

Function to insert node in an empty list,

struct Node *addToEmpty(struct Node *tail, int data)
{
    // If the list is not empty
    if(tail != NULL)
    {
        return tail;
    }

    //Create a node dynamically
    tail = (struct Node *)malloc(sizeof(struct Node *));

    //Assign the data
    tail->data = data;

    //As there is only one node, we point the single node to itself
    tail->next = tail;

    return tail;
}

In the above code, the start node and the tail node is same, as we added to the empty circular linked list.

 

Insertion at the beginning of the list

To insert a node at the beginning of the list, follow the below steps:

• Create a node , say T
• Make T-> next = last->next
• last->next = T

                                    

Function to insert node in the beginning of the circular linked list,

struct Node *addBegin(struct Node *tail, int data)
{
    if (tail == NULL)
        return addToEmpty(tail, data);

    //Create a node dynamically.
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));

    //Assigning the data
    temp->data = data;

    //Adjusting the links
    temp->next = tail->next;
    tail->next = temp;

    return tail;
}

In the above code, the new node is inserted at the beginning and tail pointer remains same after insertion.

 

Insertion at the end of the List

To insert a node at the end of the list, follow the below steps:

• Create a new node T.
• Make T->next = last->next
• Last->next = T
• Last = T

                            

Function to insert the new node at the end of the list:

struct Node *addEnd(struct Node *tail, int data)
{
    if (tail == NULL)
        return addToEmpty(tail, data);

    //Create a node dynamically.
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));

    //Assign the data
    temp->data = data;

    //Adjusting the links
    temp->next = tail->next;
    tail->next = temp;
    tail = temp;

    return tail;
}

struct Node *addAfter(struct Node *tail, int data, int search)
{
    if(tail == NULL)
        return NULL;

    struct Node *temp, *p;
    p = tail->next;

    //Search the given number
    do
    {
        if(p->data == search)
        {
            //Create a node dynamically
            temp = (struct Node *)malloc(sizeof(struct Node));

            //Assigning the data
            temp->data = data;

            //Adjusting the links
            temp->next = p->next;
            p->next = temp;

            if(p == tail)
                tail = temp;

            return tail;
        }
        p = p->next;
    } while (p != tail->next);

    printf("The given item is not present in the list");
    return tail;
}

void deleteNode(struct Node* head, int key) 
{ 
    if (head == NULL) 
        return; 
  
    // Find the required node 
    struct Node *curr = head, *prev; 
    while (curr->data != key) { 
        if (curr->next == head) { 
            printf("\nGiven node is not found in the list"); 
            break; 
        } 
  
        prev = curr; 
        curr = curr->next; 
    } 
  
    // Check if node is only node 
    if (curr->next == head) { 
        head = NULL; 
        free(curr); 
        return; 
    } 
  
    // If more than one node, check if 
    // it is first node 
    if (curr == head) { 
        prev = head; 
        while (prev->next != head) 
            prev = prev->next; 
        head = curr->next; 
        prev->next = head; 
        free(curr); 
    } 
  
    // check if node is last node 
    else if (curr->next == head) { 
        prev->next = head; 
        free(curr); 
    } 
    else { 
        prev->next = curr->next; 
        free(curr); 
    } 
}

• Any node can be starting point in circular linked list. We can traverse the list by starting from any point. The traversing should stop when the first visited node is visited again.
• It is used in implementation of queue. Unlink this implementation; we don’t need to maintain two pointers for front and rear if we use the circular linked list. Here, we maintain the pointer to the last inserted node and front can always be obtained as next of last.
• The main advantage of circular linked list is used in applications to repeatedly go around the list. For example, when we run multiple applications on system, it is common for the operating system to put the running applications on a list and then to cycle them, giving each of them a slice of time to execute.
• It is used in implementation of advanced data structures such as Fibonacci Heap.