Read a Linked List in Reverse Order

In this article, you will learn how to read a linked list in reverse. Note that we only have to display values in the reverse direction. We do not need to reverse the actual linked list, meaning there is no need to update pointers, etc. Reading a linked list in the backward direction is easy. We can do so by using a recursive function. Given the head of the linked list, the steps to solve the given problem are given below.

read_in_reverse(head)
If head is NULL
    return
invoke read_in_reverse by passing head.next
display the value of head

How to read a Linked List in a Reverse Order?

Consider the following figure for illustration.

In the above figure, you can see that we call the read_in_reverse() function first with the head of the linked list, i.e., the node with the value 1. Then, the same function gets called recursively by passing head.next as its argument. When the end of the list is reached, i.e., at step 5, we simply return.

After that, we display the value of the current node, i.e., the first value printed is 2, then 6, and so on. You can see that the last value read is 1 (at step 9), which is the value of the first node of the linked list.

Implementation

The following code contains the implementation of the singly linked list to insert items and display them. It is followed by the read_in_reverse() function that takes the head pointer and reads the linked list in the reverse direction.

#node for the linked list
class Node:
  def __init__(self, value=None):
    self.value = value 
    self.next = None

#implementation of linked list
class LinkedList:
  def __init__(self):
    self.head = None
    self.length = 0 #total number of elements in the linked list

  #adds a node at the end of the linked list
  def insert(self, value):
    node = Node(value) #create a node
    if self.head == None: #if list is empty insert a node at the start
      self.head = node
    else:
      temp = self.head
      #iterate through the list till last node is found
      while temp.next: 
        temp = temp.next 
      
      temp.next = node #adding a new node
      self.length += 1 #increment the length

  #traverse the complete list and print the node value
  def traverse(self):
    temp = self.head
    while temp:
      print(temp.value, end="\t")
      temp = temp.next
    print("")


def read_in_reverse(head):
  if head== None:
    return 
  read_in_reverse(head.next)
  print(head.value, end="\t")

ll = LinkedList() #create linked list

#insert values
ll.insert(1)
ll.insert(8)
ll.insert(6)
ll.insert(2)

print("Given Linked list:")
ll.traverse()

print("Reading a Linked List in Reverse")
read_in_reverse(ll.head)

Output

Given Linked list:
1	8	6	2	
Reading a Linked List in Reverse
2	6	8	1

 

Back to: Data Structure > Data Structure - Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *