Python Program to Read a Linked List in Reverse

This Python program demonstrates how to read a singly linked list in reverse order using a recursive approach.

Problem Statement

You are given the task of implementing a program to read and print a linked list in reverse order. A linked list is a data structure consisting of nodes, where each node contains data and a reference to the next node in the list.

Python Program to Read a Linked List in Reverse

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def print_reverse(self, node):
        if node is None:
            return
        self.print_reverse(node.next)
        print(node.data, end=" ")

    def reverse_print(self):
        self.print_reverse(self.head)

# Creating a linked list
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
llist.append(5)

print("Linked list in reverse:")
llist.reverse_print()

How it Works

1. Defining the Node Class:
   • The Node class defines a blueprint for creating nodes in the linked list.
   • Each node has two attributes: data to store the value of the node, and next to store a reference to the next node in the list. Initially, next is set to None.
2. Defining the LinkedList Class:
   • The LinkedList class manages the linked list as a whole.
   • It has an __init__ constructor method that initializes the linked list. It sets the initial value of the head attribute to None.
3. Appending Nodes to the Linked List:
   • The append method in the LinkedList class is used to add nodes to the end of the linked list.
   • If the linked list is empty (i.e., head is None), the new node becomes the head.
   • Otherwise, it traverses the linked list to find the last node and then adds the new node after it.
4. Printing in Reverse using Recursion:
   • The print_reverse method is used to print the linked list in reverse order using a recursive approach.
   • It takes a node as an argument.
   • Inside the method, it first checks if the given node is None. If it is, the recursion stops.
   • Otherwise, it recursively calls itself with the next node in the list. This continues until it reaches the last node.
   • During the recursive unwinding (when the recursion starts to backtrack), it prints the data of each node. Because of the recursive nature, this effectively prints the linked list in reverse order.
5. Wrapper for Reverse Printing:
   • The reverse_print method serves as a wrapper to initiate the recursive printing of the linked list in reverse.
   • It calls the print_reverse method with the initial head node of the linked list.
6. Creating and Using the Linked List:
   • An instance of the LinkedList class, named llist, is created.
   • Nodes with values 1, 2, 3, 4, and 5 are appended to the linked list using the append method.
7. Printing the Linked List in Reverse:
   • The program calls the reverse_print method on the llist object.
   • This starts the recursive process of printing the linked list in reverse order.
8. Output:
   • The program outputs the linked list elements in reverse order: “5 4 3 2 1”.

Input/ Output