We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Search a specific node in Circular Linked List
Last updated:
Searching for a specific node in a circular linked list can be done by traversing the list starting from the head node. We will continue moving to the next node until we either find the target node or return to the head, indicating that the node is not present in the list.
In this tutorial, we will understand how to search for a specific node in a circular linked list with a given Java program.
Example
Java program to find a node in a circular linked list
SearchinCLL.java
// Java program to search for a value in a circular linked list
public class SearchinCLL {
// Function to search a specific value
static void search(Node last, int key) {
// Returns, if the list is empty
if (last == null) {
System.out.println("List is an empty.");
return;
}
Node head = last.next;
Node curr = head;
// Traverse the list to find the key
while (curr != last) {
if (curr.data == key) {
// Key found
System.out.println("The key: " + key + " is found.");
return;
}
curr = curr.next;
}
// Check the last node
if (last.data == key) {
// Key found
System.out.println("The key: " + key + " is found.");
return;
}
// Key not found
System.out.println("The key: " + key + " is not found.");
}
// Print list
static void printList(Node last) {
if (last == null)
return;
Node head = last.next;
while (true) {
System.out.print(head.data + " ");
head = head.next;
if (head == last.next)
break;
}
System.out.println();
}
public static void main(String[] args) {
// Create a circular linked list
Node head = new Node(50);
head.next = new Node(20);
head.next.next = new Node(40);
head.next.next.next = new Node(10);
head.next.next.next.next = new Node(30);
head.next.next.next.next.next = head;
System.out.print("List value: ");
printList(head);
// Passing null as a node and 40 as a key
search(null, 40);
// Passing 40 as a key which is present in the list
search(head, 40);
// Passing 90 as a key which is not present in the list
search(head, 90);
}
}
Output
List value: 20 40 10 30 50
List is an empty.
The key: 40 is found.
The key: 90 is not found.
Frequently Asked Questions (FAQ)
Q1. How do you search for a value in a circular linked list?
SearchCircular.java
static int indexOf(Node head, int value) {
if (head == null) {
return -1;
}
Node current = head;
int index = 0;
do {
if (current.data == value) {
return index;
}
current = current.next;
index++;
} while (current != head);
return -1; // checked every node once
}
Q2. How does the search know the value is not present?
It stops when it returns to the starting node. At that point every node has been checked once, so the value is not in the list.
Q3. What is the time complexity of searching a circular linked list?
O(n) in the worst case and O(1) in the best case. It uses O(1) extra space.
Q4. Write a recursive search method for a circular linked list.
SearchRecursive.java
static boolean contains(Node current, Node head, int value) {
if (current.data == value) {
return true;
}
if (current.next == head) {
return false; // back at the start
}
return contains(current.next, head, value);
}
// Call: head != null && contains(head, head, value)
Q5. How do you find all positions of a value?
FindAll.java
import java.util.ArrayList;
import java.util.List;
static List<Integer> findAll(Node head, int value) {
List<Integer> positions = new ArrayList<>();
if (head == null) {
return positions;
}
Node current = head;
int index = 0;
do {
if (current.data == value) {
positions.add(index);
}
current = current.next;
index++;
} while (current != head);
return positions;
}
Q6. Can you search starting from the middle of the list?
Yes. Because the list is circular, starting at any node and stopping when you come back to it checks every node. This is useful when you already hold a reference to a recent position, such as the current song in a playlist.
Q7. How do you search in a sorted circular linked list efficiently?
Start from the smallest element (the head in a sorted circular list) and stop as soon as you pass a value larger than the target, because the value cannot appear later. The worst case is still O(n), but missing values are detected sooner.
Q8. What is a common bug in circular search?
Checking current.next != head before checking the current node, which skips the last node. Another bug is using while (current != head) without first moving off the head, which never enters the loop.
Q9. Write a Java method that returns the node before the node holding a value.
FindPrevious.java
static Node findPrevious(Node head, int value) {
if (head == null) {
return null;
}
Node previous = head;
do {
if (previous.next.data == value) {
return previous;
}
previous = previous.next;
} while (previous != head);
return null;
}
Finding the previous node is the first step of deleting a node in a singly circular list.
Q10. Why can binary search not be used on a circular linked list?
Binary search needs O(1) access to the middle element. In any linked list, reaching the middle means walking through the nodes, so binary search loses its O(log n) advantage.
