How to Detect a Circularity in a Linked List in Java
The Java Programming language contains many built-in data structures such as hash tables and linked list. However, you may find it useful to implement your own specific type of data structure based on your needs. Because of this you will often want to create your own methods to define the functionality of the data structure. While building a linked list you may wish to determine whether or not the list is circular. A circular list is one in which the end of the list refers back to the beginning of the list. Checking for this is as simple as navigating the list and determining whether or not you return to the beginning of the list.
Other People Are Reading
Instructions
-
-
1
Create a function to check for list circularity. This function will return "True" if the list is circular, and "False" otherwise. Define this function within the list class:
class LL{
public boolean isCircular(){
}
} -
2
Create a loop in the function to traverse the list. The loop will begin at the head of the function, and go through each node in the entire list, represented by the "Node" data type, until reaching "null" (the end of the list):
public boolean isCircular(){
Node current = head.next; // begins at the node following the head node
while (current != null){
}
} -
-
3
Use the loop to check each node in the list. If the current node is the head node, that means that the loop has traversed the entire list and wound up back at the beginning, which means the list is circular. If the loop hits a "null" value the list is not circular:
public boolean isCircular(){
Node current = head.next; // begins at the node following the head node
while (current != null){
if (current == head){
return True;
}
return False;
}
}
-
1
Tips & Warnings
This example is not intended to be a perfect implementation of a circular linked list or how to check it, but rather as a blue print.
