All the code snippets in this article are available in my repo: Github: Saaaaaad3

In this article, we will refer to the fundamentals of Java to learn about data structure as java seems to be one of the most popular languages when it comes to learning about data structures.

Prerequisites:

Singly Linked Lists (https://bigsmallbyte.hashnode.dev/singly-linked-list)

Getting To Know

After learning about singly and doubly linked lists, we will move on to another type of linked list, though it is not used as much as the other two, but it is handy to know about it. Circular Linked lists are exactly what the name suggests, they are circular in the sense that the tail’s next is pointing to a node of the list instead of pointing to a null.

It does not introduce a new pointer on anything, it is the same as a singly linked list. We can certainly make a doubly list as a circular linked list as well.

Display Function, but with Limits!

In a non-circular linked list, the execution of the display function goes like this:

Check if head is null or not.
Make a temporary head node.
Iterate till null(tail’s next) is encountered.

But as explained earlier, the next pointer of tail is pointed towards another node of our list. This will cause the loop of the display function to spiral into an endless or infinite loop, as our temporary head pointer will never encounter a null.

To avoid such a scenario of an infinite loop, we can add a simple limit as to how many times the while loop will run.

The count variable will keep the count of iteration
Add the size of the list and max (accepted as a parameter). This makes sure that AT LEAST, the full list has been iterated.
Run the while loop till a null is not encountered (in case the list is not circular) and the count is smaller than size+max.

    public void DisplayWithLimit(int max){
        if(head == null){
            System.out.println("List is Empty");
            return;
        }
        Node tempNode = head;
        int count = 0;

        while(tempNode != null && size + max > count){
            if(tempNode == tail){
                System.out.print("'"+tempNode.value+"'" + "->");
            }
            else {
                System.out.print(tempNode.value + "->");
            }
            tempNode = tempNode.next;
            count++;
        }
        System.out.print("End");
        System.out.println();
    }

Checking for a Cycle

Before we can operate on Circular linked lists, it is important to know if the list is circular or not.

To do so, we can use Floyd’s cycle finding algorithm or famously known as the Hare-Tortoise algorithm.

In this approach we have two pointers let's say FastPntr and SlowPntr
The FastPntr moves by skipping 1 node and the SlowPntr will move from node to node.
If there exists a cycle, both the points will eventually meet at a common node.
If both the pointers are on the same node, we can conclude that the given linked list is indeed a circular linked list.

If somehow the FastPntr is null, we can say that the given linked list is not a circular linked list.

    public boolean CycleExists() {
        if (head == null) {
            System.out.println("List is Empty");
            return false;
        }
        return PointersMeet(head) != null;
    }
    private Node PointersMeet(Node head) {
        Node fastPtnr = head;
        Node slowPtnr = head;

        do {
            if (fastPtnr.next == null || fastPtnr.next.next == null) {
                return null;
            }

            slowPtnr = slowPtnr.next;
            fastPtnr = fastPtnr.next.next;
        }
        while (slowPtnr != fastPtnr);

        return slowPtnr;
    }

Make Cycle in a non-circular linked list

To add a cycle to a non-circular linked list is fairly easy, given the condition that you are maintaining the tail in the code. We can simply point the next pointer of tail to the node at the index provided in the parameter.

Just in case you are not maintaining the tail (why would you do that though?) we can simply iterate till we encounter a null. By doing so we will have the last node, and point the next of our last node to the index of the node.

    public void makeCycleAt(int index){
        if(head == null){
            System.out.println("List is Empty");
            return;
        }
        if(CycleExists()){
            System.out.println("Cycle Already Exists");
            return;
        }
        int count = 0;
        Node tempNode = head;

        while(count < index){
            tempNode = tempNode.next;
            count++;
        }
        tail.next = tempNode;
        cycleHead = tempNode;
    }

A little tip here, just like we maintain head and tail pointers, we can also add a cycleHead which will hold the node from where the cycle starts. This will improve the time complexity of the functions which may need the start of the cycle, as we will not have to run another function with a loop to figure out the start of a cycle.

To break the cycle simply make the next pointer of the tail to point at null.

tail.next = null;

This part was fairly short as most of the functions are the same as the singly linked list. Nevertheless, many more functions can be created with the help of cycleHead which we saw in the last section of the article.

This was the basics of what a circular linked list is in order to help you get the gist of it.