package com.thealgorithms.datastructures.lists;
/**
* The SearchSinglyLinkedListRecursion class extends SinglyLinkedList and provides
* a method to search for a value in a singly linked list using recursion.
* <p>
* This class demonstrates a recursive approach to check if a given integer value is
* present in the linked list. The search method calls a private recursive helper method
* `searchRecursion`, which checks each node's value and moves to the next node if necessary.
* </p>
* <p>
* Example:
* Given a list containing the values 1 -> 2 -> 3 -> 4, calling search(3) will return `true`,
* while calling search(5) will return `false`.
* </p>
* <p>
* Complexity:
* <ul>
* <li>Time Complexity: O(n), where n is the number of nodes in the linked list.</li>
* <li>Space Complexity: O(n), due to the recursive call stack in the worst case.</li>
* </ul>
* </p>
*/
public class SearchSinglyLinkedListRecursion extends SinglyLinkedList {
/**
* Recursively searches for a given value in the linked list.
*
* @param node the head node to start the search.
* @param key the integer value to be searched for.
* @return {@code true} if the value `key` is present in the list; otherwise, {@code false}.
*/
private boolean searchRecursion(Node node, int key) {
return (node != null && (node.value == key || searchRecursion(node.next, key)));
}
/**
* Public search method to determine if a key is present in the linked list.
*
* @param key the integer value to be searched for.
* @return {@code true} if the value `key` is present in the list; otherwise, {@code false}.
*/
@Override
public boolean search(int key) {
return searchRecursion(getHead(), key);
}
}