### Circular Linked List | Insertion

So Far, we have discussed Singly Linked list , Doubly Linked list we will discuss about the circular Linked list which do not have NULL field at the tail node.

**Why there is need of Circular Linked list ?**

In both singly and doubly Linked list , the ends are indicated with the NULL values and start are marked with HEAD values.

Circular Linked lists are those list which does not have a NULL end point. In fact , the Last node of the circular linked list point to the head making it a closed linked list.

### Advantages of Circular Linked list :-

1: This can be used for the implementation of queue.

2: This can be useful in a situation when multiple applications are running on PC , and we have to make sure that all the processes access the resource in a cycle. This is also called Round Robin Algorithm.

3: These are useful for the implementation for the Fibonacci Heap.

### Printing the Elements of the Circular Linked List

We know that the list is being accessed by the head node. Since, all nodes are arranged in the circular, the last node will be pointing to the head node, which means the next pointer of the tail node will be pointing to the head of the node.

Now, start from the head node and print the data of the node until we reach the head node again.

Time Complexity : O(n) , for printing the complete list of size n.

Space Complexity : O(1) , for storing one temporary variable.

A node can be inserted in the Circular linked list in three ways:-

- Inserting node at the beginning of Circular the linked list
- Inserting node at the middle of the Circular linked list (at any random position)
- Inserting a node at the end of the Circular linked list.

We will look to all 3 cases one by one :-

### Insertion at the beginning Circular Linked list

A node is inserted before the current head node.

- A new node is created and initially keep it’s next pointer pointing to itself.

- Now, Update the next pointer of the new node with the head and traverse the linked list until the tail.

- Now, the loop stops at the tail node and update the next pointer of tail to the new node.

- Mark the new node as the head of the circular linked list.

Time Complexity : O(n) , for traversing the complete list of size n.

Space Complexity : O(1) , for storing one temporary variable.

### Insertion at the end of Circular Linked list

In this case ,we need to place the new node just after the tail node and update the tail next pointer to head.

- Firstly, create a new node and keep its next pointer to itself.

- Now, run the loop till tail node and point the next of the new node to the head node.

- Now , at the tail node, update the next pointer of the tail node to point towards the new node.

Time Complexity : O(n) , for traversing the complete list of size n.

Space Complexity : O(1) , for storing one temporary variable.

### Insertion at any position in Circular Linked List

This insertion is quite similar to the insertion of node at any position in the linked list.

In this we will be given a position where we have to insert the linked list and also we need to modify the two ‘next’ pointers.

Consider , if we want to add a new node at position 3 , then we will traverse the linked list upto second position and modify the next pointers of the two nodes i.e new node points to the next node of the position where we want to add this node.

( Note :- As indexing starts from zero , so to insert at position 3 , we will run the loop till 2 position ).

- Search the node after which you want to insert the new node.

- Perform the following steps:-

- New_node->next = temp_node->next;
- Temp_node->next =new_node.

Time Complexity : O(n) , for traversing the complete list of size n.

Space Complexity : O(1) , for storing one temporary variable.

### Full Implementation of Circular Linked list

#include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node *next; }; struct Node *addToEmpty(struct Node *head, int data) { if (head!= NULL) return head; struct Node *temp =(struct Node*)malloc(sizeof(struct Node)); temp -> data = data; head= temp; head-> next = head; return head; } struct Node *addtoBegin(struct Node *head, int data) { if (head== NULL) return addToEmpty(head, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = head-> next; head-> next = temp; return head; } struct Node *addtoEnd(struct Node *head, int data) { if (head== NULL) return addToEmpty(head, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = head-> next; head-> next = temp; head= temp; return head; } struct Node *addatpos(struct Node *head, int data, int item) { if (head== NULL) return NULL; struct Node *temp, *p; p = head-> next; do { if (p ->data == item) { temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = p -> next; p -> next = temp; if (p == head) head= temp; return head; } p = p -> next; } while(p != head-> next); cout << item << " not present in the list." << endl; return head; } void display(struct Node *head) { struct Node *p; if (head== NULL) { cout << "List is empty." << endl; return; } p = head-> next; do { cout << p -> data << " "; p = p -> next; } while(p != head->next); } int main() { struct Node *head= NULL; head= addToEmpty(head, 0); head= addtoBegin(head, 1); head= addtoBegin(head, 2); head= addtoEnd(head, 5); head= addtoEnd(head, 6); head= addatpos(head, 2, 8); display(head); return 0; }

CommentsNo comment yet.