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

This is a Python program to search for an element in a linked list using recursion.

Problem Description

The program prompts the user for a key to search in a linked list and displays its index.

Problem Solution

1. Create a class Node.
2. Create a class LinkedList.
3. Define methods append and display inside the class LinkedList to append data and display the linked list respectively.
4. Define methods find_index and find_index_helper.
5. find_index calls find_index_helper to search for the key recursively.
6. Create an instance of LinkedList, append data to it and display the list.
7. Prompt the user for a key to search and search for it.

Program/Source Code

Here is the source code of a Python program to search for an element in a linked list using recursion. The program output is shown below.

class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
        self.last_node = None
 
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
 
    def display(self):
        current = self.head
        while current is not None:
            print(current.data, end = ' ')
            current = current.next
 
    def find_index(self, key):
        return self.find_index_helper(key, 0, self.head)
 
    def find_index_helper(self, key, start, node):
        if node is None:
            return -1
 
        if node.data == key:
            return start
        else:
            return self.find_index_helper(key, start + 1, node.next)
 
a_llist = LinkedList()
for data in [3, 5, 0, 10, 7]:
    a_llist.append(data)
print('The linked list: ', end = '')
a_llist.display()
print()
 
key = int(input('What data item would you like to search for? '))
index = a_llist.find_index(key)
if index == -1:
    print(str(key) + ' was not found.')
else:
    print(str(key) + ' is at index ' + str(index) + '.')

Program Explanation

1. An instance of LinkedList is created.
2. Some elements are appended to the list.
3. The linked list is displayed.
4. The user is prompted for a key to search.
5. find_index_helper searches for the index. It returns -1 if the key is not found.
6. The index is displayed if found.

Subscribe Now: Python Programs Newsletter | Important Subjects Newsletters

Runtime Test Cases

Case 1:
The linked list: 3 5 0 10 7 
What data item would you like to search for? 5
5 is at index 1.
 
Case 2:
The linked list: 3 5 0 10 7 
What data item would you like to search for? 7
7 is at index 4.
 
Case 3:
The linked list: 3 5 0 10 7 
What data item would you like to search for? 4
4 was not found.

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Get Free Certificate of Merit in Python Programming Now!

« Prev - Python Program to Read a Linked List in Reverse

» Next - Python Program to Search an Element in Linked List without Recursion

Next Steps: