Python Program to Search for an Element in the Linked List using Recursion

Linked List Data Structure:

A linked list is a type of data structure that consists of a chain of nodes, each of which contains a value and a pointer to the next node in the chain.

The list’s head pointer points to the first node, and the list’s last element points to null. The head pointer points to null when the list is empty.

Linked lists can grow in size dynamically, and inserting and deleting elements from them is simple because, unlike arrays, we only need to change the pointers to the previous and next elements to insert or delete an element.

Linked lists are commonly used in the construction of file systems, adjacency lists, and hash tables.

Given an Element and LinkedList, the Task is to check whether the given element is present in the LinkedList or not in Python.

Examples:

Example1:

Input:

Given LinkedList : 5 1 7 8 9 11 13
Given Element : 9

Output:

True

Example2:

Input:

Given LinkedList : 1 9 3 5
Given Element : 2

Output:

False

Program to Search for an Element in the Linked List using Recursion in Python

Approach:

Create a class that creates a node of the LinkedList.
Create a constructor that accepts val as an argument and initializes the class variable val with the given argument val.
Initializing the next Pointer(Last Node Pointer to None i.e Null).
Create a Class Which Creates the LinkedList by connecting all the nodes.
Inside the class, the constructor Initialize the head pointer to None(Null) and the last Node pointer to Null.
Create a function addElements() inside the class which accepts the data value as an argument and add this node to the LinkedList.
Check if the lastNode Pointer is None using the if conditional statement.
If the above if condition is true(If there are no elements in the linked list) then Create a Node using the Node class by passing the data as an argument.
Initialize the head with the above node.
Else Create the new node and initialize the last node pointer Value to the new node.
Set the last node Pointer Value to the Next Pointer.
Create a Recursive function SearchElement() inside the class which accepts the element and Linkedlist Object as arguments and searches whether the given element is present in the LinkedList or not
Base case(Check if the lkdList is null or not using the if conditional statement)
If it is true then return False(Element not found as there are no elements in the LinkedList)
Check if the given element is equal to node of the LinkedList using the If condtional statement
If it is true then return True(Element is present)
Else increment the Linkedlist Pointer to the next node using the recursion
Take an object for the LinkedList Class and store it in a variable.
Add elements to the LinkedList by using the below steps.
Loop till the above number of elements using the For loop.
Give the data value as user input and store it in a variable.
Pass the above value as an argument to the addElements() function to add this value as a node to the LinkedList.
Give the element to search as user input and store it in a variable
Printing whether the element is present or not in the LinkedList by calling the SearchElement() of the above object.
The Exit of the Program.

Below is the implementation:

# Create a class that creates a node of the LinkedList.
class Node:
    # Create a constructor that accepts val as an argument and initializes the class variable val with the given argument val.
    def __init__(self, val):
        self.val = val
        # Initializing the next Pointer(Last Node Pointer to None i.e Null).
        self.nextPtr = None
  # Create a Class Which Creates the LinkedList by connecting all the nodes.


class LinkedList:
  # Inside the class, the constructor Initialize the head pointer to None(Null) and the last Node pointer to Null.
    def __init__(self):
        self.headPtr = None
        self.lastNode = None
    # Create a function addElements() inside the class which accepts the data value as an argument and add this node to the LinkedList.

    def addElements(self, val):
        # Check if the lastNode Pointer is None using the if conditional statement.
        if self.lastNode is None:
          # If the above if condition is true(If there are no elements in the linked list)
          # then Create a Node using the Node class by passing the data as an argument.
          # Initialize the head with the above node.
            self.headPtr = Node(val)
            self.lastNode = self.headPtr
        else:
          # Else Create the new node and initialize the last node pointer Value to the new node.
            self.lastNode.nextPtr = Node(val)
            # Set the last node Pointer Value to the Next Pointer.
            self.lastNode = self.lastNode.nextPtr
    # Create a Recursive function SearchElement() inside the class which accepts the element and Linkedlist Object as arguments
    # and searches whether the given element is present in the LinkedList or not

    def SearchElement(self, lkdList, elem):
      # Base case(Check if the lkdList is null or not using the if conditional statement)
        if(not lkdList):
          # If it is true then return False(Element not found as there are no elements in the LinkedList)
            return False
        # Check if the given element is equal to node of the LinkedList using the If condtional statement
        if(lkdList.val == elem):
          # If it is true then return True(Element is present)
            return True
        # Else increment the Linkedlist Pointer to the next node using the recursion
        return self.SearchElement(lkdList.nextPtr, elem)


# Take an object for the LinkedList Class and store it in a variable.
lkdList = LinkedList()
# Add elements to the LinkedList by using the below steps.
n = int(input('Enter the number of elements you wish to add in the linked list = '))
# Loop till the above number of elements using the For loop.
for i in range(n):
    # Give the data value as user input and store it in a variable.
    val = int(input('Enter data item: '))
    # Pass the above value as an argument to the addElements() function to add this value as a node to the LinkedList.
    lkdList.addElements(val)
# Give the element to search as user input and store it in a variable
elem = int(input('Enter the element to search in the LinkedList : '))
# Printing whether the element is present or not in the LinkedList by calling the SearchElement() of the above object.
print(lkdList.SearchElement(lkdList.headPtr, elem))

Output:

Enter the number of elements you wish to add in the linked list = 8
Enter data item: 11
Enter data item: 3
Enter data item: 2
Enter data item: 8
Enter data item: 6
Enter data item: 9
Enter data item: 15
Enter data item: 43
Enter the element to search in the LinkedList : 15
True