Insertion in Circular Singly Linked List

In a circular singly linked list, the last node in the list contains a pointer to the first node in the list. There is a single-linked circular list and a double-linked circular list.

Traverses a single linked circular list until it reaches the same node that started it. Such a single circular list has no beginning or end. There is no null value in the next part of any node.

The layout shown below is for a single-linked list.

singly linked list

Declaration:

You can declare a node in a circular linked list as another node, as shown below.

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

To implement a circular linked list, we keep an external “last” pointer that points to the last node in the circular linked list. So last-> next points to the first node in the linked list.

Doing this avoids having to go through the entire list when inserting a new node at the beginning or end of the list. This is because last points to the last node and last-> next points to the first node.

This was not possible if the outer pointer was pointing to the first node.

Insertion in Circular Singly Linked List:

You can insert a node in a circular linked list as the first node (empty list), first, last, or between other nodes. Let’s take a look at each of these insert operations using the figure below.

A node can be added in four ways:

  1. Insertion in an empty list.
  2. Insertion at the beginning of the list.
  3. Insertion at the end of the list.
  4. Insertion in between the nodes.

1. Insert in an empty list:

singly linked list

If the circular list has no nodes and the list is empty, the last pointer is null. Then point the last pointer to node N as above and insert a new node N. The pointer after N points to node N itself because it only has one node. Therefore, N is the first and last node in the list.

For example:

singly linked list

Here Code:

struct Node *addToEmpty(struct Node *last, int data)
{
          if (last != NULL)
          return last;
          struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
          temp -> data = data;
          last = temp;
          temp -> next = last;
          return last;
}

2. Insert at the beginning of the list:

singly linked list

As shown in the expression above, when you add a node to the beginning of the list, the pointer next to the last node points to the new node N, making it the first node.

N->next = last->next
Last->next = N

For example:

singly linked list

Here Code:

struct Node *addBegin(struct Node *last, int data)
{
          if (last == NULL)
          return addToEmpty(last, data);
          struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
          temp -> data = data;
          temp -> next = last -> next;
          last -> next = temp;
          return last;
}

3. Insert at the end of the list:

singly linked list

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

N-> next = last ->next;
last ->next = N
last = N

For example:

singly linked list

Here Code:

struct Node *addEnd(struct Node *last, int data)
{
          if (last == NULL)
          return addToEmpty(last, data);
          struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
          temp -> data = data;
          temp -> next = last -> next;
          last -> next = temp;
          last = temp;
          return last;
}

4. Insertion in between the nodes:

singly linked list

If you need to insert a new node N between N3 and N4, you must first go through the list to find the node where the new node will be inserted (in this case N3).

Once you find the node, do the following:

N -> next = N3 -> next;
N3 -> next = N

This will insert a new node N after N3.

For example:

singly linked list

Here Code:

struct Node *addAfter(struct Node *last, int data, int item)
{
          if (last == NULL)
          return NULL;
          struct Node *temp, *p;
          p = last -> 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 == last)
                                      last = temp;
                             return last;
                   }
                   p = p -> next;
          } while (p != last -> next);
          cout << item << " not present in the list." << endl;
          return last;
}

Below is a complete program that creates a single linked circular list using all of the above methods.

For example:

singly linked list

singly linked list

singly linked list

singly linked list

singly linked list

Here Code:

#include<bits/stdc++.h>
using namespace std;
struct Node
{
          int data;
          struct Node *next;
};

struct Node *addToEmpty(struct Node *last, int data)
{
          if (last != NULL)
          return last;
          struct Node *temp =
                   (struct Node*)malloc(sizeof(struct Node));
          temp -> data = data;
          last = temp;
          last -> next = last;
          return last;
}

struct Node *addBegin(struct Node *last, int data)
{
          if (last == NULL)
                   return addToEmpty(last, data);
          struct Node *temp =
                             (struct Node *)malloc(sizeof(struct Node));
          temp -> data = data;
          temp -> next = last -> next;
          last -> next = temp;
          return last;
}

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

                   (struct Node *)malloc(sizeof(struct Node));
          temp -> data = data;
          temp -> next = last -> next;
          last -> next = temp;
          last = temp;
          return last;
}

struct Node *addAfter(struct Node *last, int data, int item)
{
          if (last == NULL)
                   return NULL;
          struct Node *temp, *p;
          p = last -> 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 == last)
                                      last = temp;
                             return last;
                   }
                   p = p -> next;
          } while(p != last -> next);
          cout << item << " not present in the list." << endl;
          return last;
}
void traverse(struct Node *last)
{
          struct Node *p;
          if (last == NULL)
          {
                   cout << "List is empty." << endl;
                   return;
          }
          p = last -> next;
          do
          {
                   cout << p -> data << " ";
                   p = p -> next;
          }
          while(p != last->next);
}
int main()
{
          struct Node *last = NULL;
          last = addToEmpty(last, 6);
          last = addBegin(last, 4);
          last = addBegin(last, 2);
          last = addEnd(last, 8);
          last = addEnd(last, 12);
          last = addAfter(last, 10, 8);
          traverse(last);
          return 0;
}

Conclusion:

A circular linked list is a type of data structure that maintains a loop that is used to store the first node in the list in the last node in the linked list and is therefore called circular. These lists are useful for building continuous loops that are used in various complex data structures and games, such as the Fibonacci sequence.

Recommended Articles:

  1. Traversal in Circular Linked List
  2. How to split a circular linked list into two halves?
  3. C++ program to insert in a sorted circular linked list?
  4. How to swap nodes in a linked list without Swapping data?
  5. How to write C functions that modify head pointer of a Linked List?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 50 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
You cannot copy content of this page
Scroll Up
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.