Python Program to Display the Nodes of a Linked List in Reverse using Recursion

/ Python / By

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 a LinkedList, the task is to print all the elements of the LinkedList in Reverse order using recursion in Python.

Examples:

Example1:

Input:

Given LinkedList : 56 45 23 14 9 8 2 5 4 3 12

Output:

The Elements of the LinkedList in Reverse Order are :
12 3 4 5 2 8 9 14 23 45 56

Example2:

Input:

Given LinkedList : 1 9 3

Output:

The Elements of the LinkedList in Reverse Order are :
3 9 1

Program to Display the Nodes of a Linked List in Reverse 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 printRecursive() inside the class which accepts the temp pointer(Here value of temp pointer at first points to headptr node) of the linkedList and prints all the nodes values of the LinkedList.
  • Check if the tempPtr is null or not using the If condtional Statement(If it is null then there are no elements in the LinkedList).
  • If there are elements in the LinkedList then the value of tempPtr is not null.
  • If the tempPtr is not null then call the recursive function by pointing the next node of the tempPtr.
  • Print the value at the tempPtr node.
  • Else return.
  • 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.
  • Printing all elements of the LinkedList by passing the headPtr as an argument to the printRecursive() function.
  • 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 printRecursive() inside the class which accepts the temp pointer(Here value of temp pointer at first points to headptr node)
    # of the linkedList and prints all the nodes values of the LinkedList

    def printRecursive(self, tempPtr):
        # Check if the tempPtr is null or not using the If condtional Statement(If it is null then there are no elements in the LinkedList)
        # If there are elements in the LinkedList then the value of tempPtr is not null
        if tempPtr:
            # If the tempPtr is not null then call the recursive function by pointing the next node of the tempPtr
            self.printRecursive(tempPtr.nextPtr)
            # Print the value at the tempPtr node
            print(tempPtr.val, end=' ')
        # Else return
        else:
            return


# 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)
# Printing all elements of the LinkedList by passing the headPtr as argument to the printRecursive() function
print('The Elements of the LinkedList in Reverse Order are :')
lkdList.printRecursive(lkdList.headPtr)

Output:

Enter the number of elements you wish to add in the linked list = 11
Enter data item: 12
Enter data item: 3
Enter data item: 4
Enter data item: 5
Enter data item: 2
Enter data item: 8
Enter data item: 9
Enter data item: 14
Enter data item: 23
Enter data item: 45
Enter data item: 56
The Elements of the LinkedList in Reverse Order are :
56 45 23 14 9 8 2 5 4 3 12