Linked lists are a fundamental data structure in computer science, offering flexibility and efficiency in managing collections of data. Among the variations of linked lists, the circular linked list stands out for its unique structure and applications. In this blog post, we’ll delve into the concept of circular linked lists, explore their implementation in Java, and discuss their advantages and use cases.

Understanding Circular Linked Lists

A circular linked list is similar to a regular linked list, with the key distinction being that the last node points back to the first node, forming a circle. Unlike linear linked lists, which have a NULL pointer at the end, circular linked lists have no NULL pointers within the list itself. This circular structure allows for traversal from any node to any other node within the list.

The basic components of a circular linked list include:

• Node: A unit of data that contains both the data value and a reference (pointer) to the next node in the sequence.
• Head: A reference to the first node in the list. In a circular linked list, this node is connected to the last node, forming a circle.
• Tail: Although not always explicitly maintained, it refers to the last node in the list, which points back to the head.

How to represent a circular singly linked list in java?

A Circular Singly Linked List is similar to a singly linked list, with the difference that in a circular linked list, the last node points to the first node and not null. Instead of keeping track of the head, we keep track of the last node in the circular singly linked list.

For example:

In a Singly Linked List:

head –> 1 –> 8 –> 10 –> 16 –> null

In a Circular Singly Linked List:

last --> 16 --> 1 --> 8 --> 10 --> 
    ^____________________________|

last –> 16 –> 1 –> 8 –> 10 –> 16 // Please refer to the actual diagram for clarification.

We can insert nodes at both the end and beginning with constant time complexity.

How to implement a Circular Singly Linked List in a java ?

public class CircularSinglyLinkedList {

  private ListNode last;        // Keep track of the last node of the circular linked list   
  private int length;           // Hold the size of the circular singly list

  private class ListNode {
    private int data;
    private ListNode next;

    public ListNode(int data) {
       this.data = data;
    }
  }

  public CircularSinglyLinkedList() {
    last = null;       // When we initialize the circular singly linked list, we know the last points to null and that time the list is empty 
    length = 0;        // So the length is also 0;
  }

  // Gives the size of the circular singly linked list 
  public int length() {
    return length;
  }

  // Check whether the circular list is empty or not 
  public boolean isEmpty() {
    return length == 0;
  }


  public void createCircularLinkedList() {
    ListNode first = new ListNode(1);
    ListNode second = new ListNode(5);
    ListNode third = new ListNode(10);
    ListNode fourth = new ListNode(15);
 
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = first;      // Here we make the list in circular nature by assigning the first node 

    last = fourth;         // Last node points to the fourth node
  }


  public static void main(String[] args) {
     CircularSinglyLinkedList csll = new CircularSinglyLinkedList();
     csll.createCircularLinkedList();
  }
}

This Java class CircularSinglyLinkedList defines a circular singly linked list. It includes inner class ListNode for representing each node in the list. The class provides methods to create a circular linked list, check its length, and check whether it is empty. The main method demonstrates creating a circular linked list instance and initializing it.

How to traverse and print a circular linked list in java ?

last --> 16 --> 1 --> 8 --> 10 --> 
    ^____________________________|

Algorithm & Execution

if (last == null) {
    return;
}
ListNode first = last.next;
while (first != last) {
    System.out.println(first.data + "");
    first = first.next;
}
System.out.println(first.data + "");

The basic idea here is to find the first node using the last node, and then traverse the list from the first node to the last node. When the first node equals the last node, at that point, we are at the last node, but our while loop terminates, so we couldn’t print the last node’s data. That’s why we print it separately after the loop.

Code

public void display() {
   if (last == null) {
      return;
   }
   ListNode first = last.next;
   while (first != last) {
     System.out.println(first.data + "");
     first = first.next;
   }
   System.out.println(first.data + "");
}

This method display is designed to print the elements of the circular singly linked list. It starts from the first node, which is the node after the last node. Then, it traverses the list until it reaches the last node, printing the data of each node. Finally, it prints the data of the last node itself. If the list is empty (i.e., last is null), the method simply returns without performing any operation.

How to insert node at the beginning of a circular Singly Linked List in java ?

ListNode temp = new ListNode(data);
if (last == null) {
    last = temp;
} else {
    temp.next = last.next;
}
last.next = temp;
length++;

1. We create a temporary node (temp) which we will insert at the beginning of the circular list.
2. If the last node is null, it means our list is empty. In this case, we assign the temp node to be the last node. Both last and temp now point to the same new node we inserted. We update the last.next pointer to point to temp, forming the circular nature for the first node.
3. If the list is not empty (last is not null), we create a new temp node with the given data, and it points to null initially. Then, we update temp.next to point to last.next, so it will be added at the beginning of the last node. Even now, last and temp.next will point to the last node. We need to update the last node’s next pointer to temp so that the circular list nature remains intact.
4. Finally, we increment the length by 1 because every time we add a new node at the beginning of the last node.

Code

public void insertFirst(int data) {
  ListNode temp = new ListNode(data);
  if (last == null) {
      last = temp;
  } else {
      temp.next = last.next;
  }
  last.next = temp;
  length++;
}

This method insertFirst is designed to insert a new node with the given data at the beginning of the circular singly linked list. If the list is empty (i.e., last is null), the new node becomes both the first and last node. Otherwise, the new node is inserted after the last node, and its next reference is updated to point to the node originally after the last node. Finally, the length of the list is incremented.

How to insert node at the end of a circular singly linked list in Java?

ListNode temp = new ListNode(data);
if (last == null) {   // list is empty
   last = temp;
   last.next = last;
} else {              // if list is non-empty
   temp.next = last.next;
   last.next = temp;
   last = temp;
}
length++;

1. First, we create a new temporary node (temp) with the given data value.
2. Initially, the circular list is empty, so last will point to null, i.e., last --> null.
3. When we insert a new node, we check whether we are inserting into an empty list or a non-empty list.
4. If the list is empty, we point last to our temporary node, i.e., last = temp.
5. To create a circular structure, we need to make last.next point to last itself, i.e., last.next = last.
6. After that, we increment the length by 1 as we successfully inserted a new node into the list.
7. Now, let’s consider the scenario of a non-empty circular list. In this case, first, we assign last.next to the last node itself when there is only one node. If there is more than one node, then last.next will point to the first node, and temp.next will point to null.
8. Then, we attach the new temporary node to the end by assigning it as last.next. Previously, it pointed to itself because there was only one node. If there are more than one node, it will point to the temp node because the last node becomes the first, and temp will always become the last node to maintain the circular chain nature.
9. Finally, temp becomes our new last because it is added at the end.

So, the basic logic is to add the temporary node at the end and always make that newly inserted node the last one.

How to remove first node from a circular singly linked list in java ?

if (isEmpty()) {
   throw new NoSuchElementException();
}
ListNode temp = last.next;
if (last.next == last) {
   last = null;
} else {
   last.next = temp.next;
}
temp.next = null;
length--;
return temp;

1. If the list is empty, meaning there are no elements to remove, we throw a NoSuchElementException.
2. We create a temporary node temp which will store the node to be removed, i.e., the first node (last.next).
3. If last.next points to last itself, it means there is only one node in the list. In this case, we remove the last node by assigning null to last.
4. If last.next doesn’t point to last, it means there are multiple nodes in the list. We remove the first node by updating last.next to point to the second node (temp.next).
5. We then set temp.next to null to detach temp from the list.
6. We decrement the length of the list by 1 since we have successfully removed a node.
7. Finally, we return the removed node temp.

So, the main logic is to remove the first node by adjusting pointers and then returning the removed node.

Advantages of Circular Linked Lists

Circular linked lists offer several advantages over their linear counterparts:

1. Efficient Insertion and Deletion: Insertion and deletion operations can be performed quickly, especially at the beginning or end of the list, as there’s no need to traverse the entire list.
2. Circular Traversal: With a circular structure, traversal from any point in the list to any other point becomes straightforward.
3. Memory Efficiency: Circular linked lists save memory by eliminating the need for a NULL pointer at the end of the list.

Use Cases of Circular Linked Lists

Circular linked lists find applications in various scenarios, including:

• Round-Robin Scheduling: In operating systems, circular linked lists are used to implement round-robin scheduling algorithms, where tasks are executed in a circular order.
• Music and Video Playlists: Circular linked lists can be used to implement circular playlists, allowing seamless looping from the last item to the first.
• Resource Management: In resource allocation systems, circular linked lists can represent a pool of resources where allocation and deallocation operations are frequent.

Conclusion

Circular linked lists provide an elegant solution to certain problems by leveraging their circular structure and efficient operations. In Java, implementing a circular linked list involves managing node connections carefully to maintain the circular property. Understanding the strengths and applications of circular linked lists can aid in designing efficient algorithms and data structures for various computational tasks.