Python Program to Count the Occurrences of Elements in a Linked List using Recursion

This is a Python program to count the number of occurrences of an element in a linked list using recursion.

Problem Description

The program prompts the user for a key and displays the number of times the key occurs in the linked list.

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 count and count_helper.
5. count calls count_helper to count the linked list recursively.
6. Create an instance of LinkedList, append data to it and display the list.
7. Prompt the user for a key and display the number of times it occurs by calling the method count.

Program/Source Code

Here is the source code of a Python program to count the number of occurrences of 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:
            print(current.data, end = ' ')
            current = current.next
 
    def count(self, key):
        return self.count_helper(self.head, key)
 
    def count_helper(self, current, key):
        if current is None:
            return 0
 
        if current.data == key:
            return 1 + self.count_helper(current.next, key)
        else:
            return self.count_helper(current.next, key)
 
a_llist = LinkedList()
for data in [7, 3, 7, 4, 7, 11, 4, 0, 3, 7]:
    a_llist.append(data)
print('The linked list: ', end = '')
a_llist.display()
print()
 
key = int(input('Enter data item: '))
count = a_llist.count(key)
print('{0} occurs {1} time(s) in the list.'.format(key, count))

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 enter.
5. count_helper counts the number of times the key occurs in the list.
6. The count determined is then displayed.

Runtime Test Cases

Case 1:
The linked list: 7 3 7 4 7 11 4 0 3 7 
Enter data item: 3
3 occurs 2 time(s) in the list.
 
Case 2:
The linked list: 7 3 7 4 7 11 4 0 3 7 
Enter data item: 7
7 occurs 4 time(s) in the list.
 
Case 3:
The linked list: 7 3 7 4 7 11 4 0 3 7 
Enter data item: 2
2 occurs 0 time(s) in the list.

Sanfoundry Global Education & Learning Series – Python Programs.

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

Subscribe Now: Python Programs Newsletter | Important Subjects Newsletters

« Prev - Python Program to Reverse a Linked List without Recursion

» Next - Python Program to Count the Occurrences of Elements in a Linked List without Recursion

Related Posts:

Recommended Articles: