C++

Circular Linked List in C++

We can put items into the circular linked list from anywhere in the list; however, we cannot insert elements into the array from anywhere in the list since it is in contiguous memory. The last element in a circular linked list keeps the address of the next element, while the last element keeps the address of the first element. A circular chain is formed by the elements referring to one another in a circular pattern.

As the circular linked list has a dynamic size, memory may be allocated only when it is needed. The article will demonstrate the circular linked list with the C++ program illustrations in c++.

Application of Circular Linked List

A circular linked list is one in which all of the nodes are connected in a circle. There is no NULL element in the circular linked list. A beginning point can be any node. Starting from any place in the list, we may traverse the entire list. All we have to do now is wait till the first node is reached again. There we have some applications of a circular linked list as follows:

  1. Our personal computers, which run several apps, are an example of how the circular linked list is utilized in real life. All running apps are stored in a circular linked list, and the OS assigns each one a certain time slot to execute. The Operating System continues to loop over the linked list until all the programs are executed.
  2. Multiplayer games are another excellent example. All of the players are stored in a circular linked list, with the pointer moving ahead when each player’s opportunity expires.
  3. The circular Queue may be created using a Circular Linked List as well. We must retain both pointers, FRONT, and REAR, in memory at all times in a Queue, but only one pointer is needed in a Circular Linked List.

Example 1: Creating Circular Linked List Traversal in C++

The only difference is that in a circular linked list, the Node at the last position will have its next link to the Head of the List, whereas, in a linear linked list, the last Node would have its next point to the Bottom of the List. The implementation of circular linked list traversal code in C++ is shown below.

In the first step, we have defined a class as “Node”, in which we have declared an int variable as “MyData”. The variable “MyData” is the data for the node. The pointer is also declared in this class as “next” for the pointer to the next node in the circular linked list.

After the class “Node”, we have a function called “push”, which inserts the node at the beginning of the circular linked list. We defined the constructor, which passes the head_node pointer reference of the class “Node” and the variable “MyData” as a parameter. The new pointer is created as “MyPtr”, which has called and assigned the “Node”.

Then, the temp pointer is declared as “temp”, which has the head_node. There are pointers such as “ptr1” and “ptr2” which are called “MyData” and pointer “next” and take their addresses. After that, we have an if statement in which there is only head_node, and it is kept null. If the circular linked list is NULL, then add the next to the last node with the help of a while loop. Otherwise, the else statement will be executed in which the Head points to the List’s first Node.

Then, we have created another function as “DisplayList”, and in the constructor of this function, we have just passed the node head of the circular linked list. The function will display the Nodes in a Circular linked list through a do-while loop after the if statement, which has the condition that the head of the node should not be equal to null.

Finally, there is the main method, which will test the implementation described previously. The pointer head of the class “Node” has been set to “NULL” in the main method. Then, add the data to the linked list with the help of the push() method. The “head” is passed to the function “DisplayList”, which will show the circular linked list.

#include <bits/stdc++.h>

using namespace std;

class Node
{
    public:
    int MyData;
    Node *next;
};
void push(Node **head_node, int MyData)
{
    Node *MyPtr1 = new Node();
    Node *temp = *head_node;
    MyPtr1->MyData = MyData;
    MyPtr1->next = *head_node;
    if (*head_node != NULL)
    {
        while (temp->next != *head_node)
            temp = temp->next;
            temp->next = MyPtr1;
    }
    else
        MyPtr1->next = MyPtr1;
    *head_node = MyPtr1;
}

void DisplayList(Node *head)
{
    Node *temp = head;
    if (head != NULL)
    {
        do
        {
cout<MyData<next;
        }
        while (temp != head);
    }
}
int main()
{
    Node *head = NULL;
push(&head, 2001);
push(&head, 2015);
push(&head, 2006);
push(&head, 2022);
cout<< "Circular Linked List:\n ";
DisplayList(head);
cout<< "\n ";
    return 0;
}

The circular linked list implemented in the above code output is displayed in the following image.

Example2: Divide the Circular Linked List into Two Halves in C++

The following program makes splitting a circular linked list into two parts possible. Let’s look at the implementation of how we split the circular linked list in c++.

First, we have a class “Node” where we have defined a variable “items” and the pointer “next” of the Node. The members of the class “Node” are public in this program. Then, we built a function called “HalveList ” in which we split the list from the beginning with the head into two lists. The head1_node and head2_node are references to the two resultant linked lists’ head nodes.

In the function, we have declared two pointers, “s_ptr” and the “f_ptr”, which has the head of the linked list. If the if statement is used for the head node containing a null value, then we have a while loop that states that f_ptr->next becomes head if the circular list has odd nodes, and f_ptr->next->next becomes head if the list contains even nodes.

After the while loop, we have again used the if statement in which the condition is “if the list contains even numbers of elements, f_ptr should be moved and set the head1_node pointer of the first half”. In the next if statement, we have set the head2_node to the second half of the linked list.

We have assigned the s_ptr->next to the f_ptr->next to make the second half-circular of the list, and then s_ptr-> is kept equal to the head of the list and makes the first half circle.

The second function is created as “push”, which is utilized to insert a node at the start of a circular linked list with this function. In the function, the condition implies if the head_node of the circular linked list is not null, then set next to the last node. The third function, “DisplayList”, is generated for the circular linked list to be displayed.

Then, we have the main function, where we have initialized the head, head1_node, and head2_node empty. The push method is used to insert the values in the linked list, and through the cout command, the circular linked list and the split circular linked list will be displayed.

#include <bits/stdc++.h>

using namespace std;

class MyNode
{
    public:
    int items;
MyNode *next;
};
void HalveList(MyNode *head,MyNode **head1_node,MyNode **head2_node)
{
MyNode *s_ptr = head;
MyNode *f_ptr = head;  
if(head == NULL)
        return;
    while(f_ptr->next != head &&
f_ptr->next->next != head)
    {
f_ptr = f_ptr->next->next;
s_ptr = s_ptr->next;
    }
    if(f_ptr->next->next == head)
f_ptr = f_ptr->next;
    *head1_node = head;
    if(head->next != head)
        *head2_node = s_ptr->next;
f_ptr->next = s_ptr->next;
s_ptr->next = head;
}

void push(MyNode **head_node, int items)
{
MyNode *NewPtr = new MyNode();
MyNode *temp = *head_node;
NewPtr->items = items;
NewPtr->next = *head_node;
if(*head_node != NULL)
    {
        while(temp->next != *head_node)
        temp = temp->next;    
        temp->next = NewPtr;
    }
    else
NewPtr->next = NewPtr; /*For the first MyNode */

    *head_node = NewPtr;
}
void DisplayList(MyNode *head)
{
MyNode *temp = head;
if(head != NULL)
    {
cout<<endl;
        do {
cout<items <next;
        } while(temp != head);
    }
}

int main()
{
    int MyListSize, i;
MyNode *head = NULL;
MyNode *head1 = NULL;
MyNode *head2 = NULL;

push(&head, 10);
push(&head, 90);
push(&head, 40);
push(&head, 70);

cout<< "Circular Linked List";
DisplayList(head);    
HalveList(head, &head1, &head2);

cout<< "\nFirst Halve Circular Linked List";
DisplayList(head1);

cout<< "\nSecond Halve Circular Linked List";
DisplayList(head2);
    return 0;
}

Here we have the output of the original circular linked list, the output of the first half-circular linked list, and the second half of the circular linked list.

Example 3: Sorting the Circular Linked List in C++

In the first step, we have a class “NodeList”, which contains member variables and pointers in the class. Then, we have created a function “SortInsertion”, which inserts a new node in a sorted list. This function requires a pointer to the head node because it can change the input linked list’s head.

After that, we have an if statement for NodeList, which contains only node in it. The head_node point to the new node. In the else, if statement, we have assigned the data of the NodeList to current.

Here, a new node is added before the head node. The if-else block has a while loop that has a condition; If the value is less than the head value, the next or last node must be changed. The while loop will just Identify the node before the insertion point.

After that, we made a new_NodeList, the next node that locates the pointer’s next node. Then, current->next, we have to change the pointer’s location to the next. For printing the nodes of the linked list, we have called a function “ShowList”.

In the end, we have the main function where we have initialized an array and iterated over the specified array, which will be a sorted array.

#include <bits/stdc++.h>

using namespace std;

class NodeList
{
    public:
    int Values;
NodeList *next;
};
void SortInsertion(NodeList** head_node, NodeList* new_NodeList)
{
NodeList* current = *head_node;  
    if (current == NULL)
    {
new_NodeList->next = new_NodeList;
        *head_node = new_NodeList;
    }
    else if (current->Values >= new_NodeList->Values)
    {
        while(current->next != *head_node)
            current = current->next;
        current->next = new_NodeList;
new_NodeList->next = *head_node;
        *head_node = new_NodeList;
    }


    else
    {
        while (current->next!= *head_node&&
            current->next->Values Values)
        current = current->next;

new_NodeList->next = current->next;
        current->next = new_NodeList;
    }
}
void showList(NodeList *begin)
{
NodeList *temp;

if(begin != NULL)
    {
        temp = begin;
        do {
cout<Values<next;
        } while(temp != begin);
    }
}

int main()
{
    int MyArr[] = {31, 5, 23, 99, 30};
    int list_size, i;

NodeList *begin = NULL;
NodeList *temp;

    for (i = 0; iValues = MyArr[i];
SortInsertion(&begin, temp);
    }  
cout<<"Sorted Circular Linked List:\n";
showList(begin);
cout<<"\n";
    return 0;
}

The sorted circular linked list is displayed on the following screen of Ubuntu.

Conclusion

This ends our discussion of how to insert, split, and sort nodes in a circular linked list in C++. A circular linked list is used in many applications that demand a lot of flexibility. I hope this will help you to remove ambiguity related to the circular linked list in C++.

About the author

Kalsoom Bibi

Hello, I am a freelance writer and usually write for Linux and other technology related content