A singly linked list is a data structure that has a sequence of nodes. A node contains data and a reference to the next node. We can find a node with the given value in the linked list using two approaches, i.e., iterative or recursive. In this article, we will use the recursive approach to search for an element in the linked list.

Step for Searching a Linked List for an Element using Recursion

The search method takes the current node curr_node of the linked list, the value to search, and an index. Initially, we pass the head of the linked list as curr_node and 0 as the index value.

If curr_node is NULL, then no node with the given value is found, and therefore, we return NULL.

If the value at curr_node is equal to the given one, then the node with the given value is found. We return that node and its index in the linked list.

Otherwise, we continue our recursive search and advance the linked list by passing curr_node.next to the search method. We also increment the value of the index when calling the search function.

Implementation of Linked List search using Recursion

The implementation of the recursive search is given as follows:

#node for the linked list
class Node:
  def __init__(self, value=None):
    self.value = value 
    self.next = None

#implementation of linked list
class LinkedList:
  def __init__(self):
    self.head = None
    self.length = 0 #total number of elements in the linked list

  #adds a node at the end of the linked list
  def insert(self, value):
    node = Node(value) #create a node
    if self.head == None: #if list is empty insert a node at the start
      self.head = node
    else:
      temp = self.head
      #iterate through the list till last node is found
      while temp.next: 
        temp = temp.next 
      
      temp.next = node #adding a new node
      self.length += 1 #increment the length

  
  #traverse the complete list and print the node value
  def traverse(self):
    temp = self.head
    while temp:
      print(temp.value, end="\t")
      temp = temp.next
    print("")


def  search_recursive(curr_node, value, index=0):
  if curr_node == None: #element not found
    return None
  if curr_node.value == value: #node with the given value found
    return index, curr_node
  else:
    return search_recursive(curr_node.next, value, index+1) #advance the linked list and increase the value of index

Output
ll = LinkedList() #create list_1

#insert values
ll.insert(1)
ll.insert(8)
ll.insert(6)
ll.insert(2)
ll.insert(3)
ll.insert(0)

print("Linked list:")
ll.traverse()

value = 3
index, node = search_recursive(ll.head, 3)
print(f"The index of the given value {value} is:", index)

Output

1	8	6	2	3	0	
The index of the given value 3 is: 4