This is a Python program to search for an element in a linked list using recursion.
The program prompts the user for a key to search in a linked list and displays its index.
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.
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) + '.')
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.
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.