Search a in Circular Linked List

Q: How do you search for a value in a circular linked list?

Java example: 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 }

Q: 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.

Q: Write a recursive search method for a circular linked list.

Java example: 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)

Q: How do you find all positions of a value?

Java example: import java.util.ArrayList; import java.util.List; static List findAll(Node head, int value) { List 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; }

Q: 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.

Search a specific node in Circular Linked List

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.

Was this tutorial helpful?

Help Us Improve

Search a specific node in Circular Linked List

Example

Java program to find a node in a circular linked list

Frequently Asked Questions (FAQ)