Table of contents
1.
Introduction
2.
Algorithm
2.1.
Implementation
2.2.
Complexities
2.3.
Frequently Asked Questions
2.4.
What is the major difference between a Singly-Linked List and a Circular Linked List?
2.5.
What is the time complexity of inserting an element in a Circular Linked List?
3.
Conclusion
Last Updated: Mar 27, 2024
Medium

Singly Linked List To Circular Linked List

Author Ishita Chawla
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

Introduction

The circular linked list is also a type of the singly linked list, the sole difference being that its last node points to the first node, so its link part holds the address of the first node. While the linked part of the last node of the singly linked list always contains a NULL value. A circular linked list can be traversed in any direction, either clockwise or anticlockwise, as it has no starting or ending node. (See, Traversal of a Circular Linked List)

A singly linked list looks like this:

Singly Linked List

While a circular linked list looks like this:

Circular Linked List

Circular linked lists are useful in repeatedly going over the list and are also used to implement advanced data structures.

This blog will discuss how to convert a singly linked list to a circular linked list.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Algorithm

The algorithm is quite simple:

  • Traverse the linked list and find the last node.
  • If the node is the last node and points to NULL, make it point to the head node.
  • The singly linked list has now been converted into the circular linked list.

Implementation

// C++ program to convert a singly linked list to a circular linked list.
#include <iostream>
using namespace std;
 
// 'NODE' class to store linked list nodes.
class Node
{
 
public:
    int data;
    Node *next;
 
    // Constructor to create a node with given data.
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{
 
    // 'HEAD' pointer to store the address of the first node.
    Node *head;
 
public:
    LinkedList()
    {
        head = NULL;
    }
 
    // To print the elements of the circular linked list.
    void printLinkedList()
    {
        Node *current = head;
 
        // Displaying the nodes of the linked list.
        while (current->next != head)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << current->data << " ";
    }
 
    // Function to insert nodes in the linked list.
    void insert(int data)
    {
 
        /*  If linked list is empty, create a new node
            and direct the 'HEAD' node to the newly created node.
        */
        if (head == NULL)
        {
            head = new Node(data);
            return;
        }
 
        // Else traverse the linked list until the end of the list is encountered.
        Node *current = head;
        while (current->next)
        {
            current = current->next;
        }
 
        // Create and insert a new node at the end of the linked list.
        current->next = new Node(data);
    }
 
    // Function to convert a singly linked list to a circular linked list.
    void circular()
    {
        // Declaring a node variable and assigning the head node to it.
        Node *current = head;
 
        // If the next node to the current node is not NULL, the head points to the next node.
        while (current->next != NULL)
            current = current->next;
 
        // If the next node to the current node is NULL, the head points to the first node.
        current->next = head;
        head = current;
    }
};
 
int main()
{
    int n, data;
 
    // Taking user input.
    cout << "Enter the size of the linked list: ";
    cin >> n;
 
    LinkedList *givenList = new LinkedList();
 
    cout << "Enter the values of the nodes: \n";
    for (int i = 0; i < n; i++)
    {
        cin >> data;
        givenList->insert(data);
    }
 
    // Call the function to convert the singly linked list to a circular linked list and print it.
    givenList->circular();
    printf("The circular linked list is: \n");
    givenList->printLinkedList();
 
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

Enter the size of the linked list: 6

Enter the values of the nodes: 

8 6 14 19 23 10

Output

The circular linked list is: 

10 8 6 14 19 23

Complexities

Time Complexity

O(N), where N is the size of the linked list.

Since we are traversing the entire linked list, the time complexity is given by O(N).

Space Complexity

The space complexity is O(1)

The space complexity is constant as we are not using extra space except for variables.

Note: If we maintain the tail pointer along with the head pointer in our singly linked list then it can be converted to a circular linked list in O(1) time by updating the next pointer of the tail with the head.

Also read - Merge sort in linked list

Frequently Asked Questions

What is the major difference between a Singly-Linked List and a Circular Linked List?

A Singly-Linked List has a null pointer after the last node meaning it has an end and a beginning whereas a Circular Linked List much like a circle has no beginning and no end. Any of the nodes could be considered as the starting or ending nodes.

What is the time complexity of inserting an element in a Circular Linked List?

The time complexity of the insertion of an element in a Circular Linked List is O(N) where N is the size of the Linked List

Conclusion

So, this blog discussed how to convert a singly linked list to a circular linked list. To learn more, head over right now to Coding Ninjas Studio to practice problems on topics like Linked ListGraphs, and Trees, and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

Recommended Reading:

Problems based on Circular Linked List

Problems based on Singly Linked List

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass