Python Program to Search an Element in a Linked List using Recursion

In this Python program, we will implement a recursive approach to search for an element in a linked list. A linked list is a data structure where each element (node) contains a value and a reference to the next element in the list. We’ll define a class for the linked list, and then implement a recursive function to search for a given element within the list.

Problem Statement

In this Python program, we will implement a recursive approach to search for an element in a linked list. A linked list is a data structure where each element (node) contains a value and a reference to the next element in the list. We’ll define a class for the linked list, and then implement a recursive function to search for a given element within the list.

Python Program to Search an Element in a Linked List using Recursion

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def search_recursive(self, current, target):

        if current is None:
            return False
        if current.value == target:
            return True
        return self.search_recursive(current.next, target)
    
    def search(self, target):
        return self.search_recursive(self.head, target)

linked_list = LinkedList()
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)
linked_list.append(40)

search_element = 20

if linked_list.search(search_element):
    print(f"Element {search_element} found in the linked list.")
else:
    print(f"Element {search_element} not found in the linked list.")

How it works

1. The program defines a Node class to represent the elements in the linked list.
2. It defines a LinkedList class with methods to append elements to the end of the linked list and to search for an element using recursion.
3. The search_recursive method is a recursive function that takes a current node and the target element as parameters. It returns True if the target element is found, otherwise, it recursively calls itself with the next node.
4. The search method initiates the search by calling the search_recursive method with the head of the linked list.
5. The program creates a linked list, appends elements, and then searches for a specific target element using the search method.
6. The result of the search is printed to the console.

Input / Output