Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction to the problem statement 
2.
Method 1: Using auxiliary space, stack 
2.1.
Algorithm 
2.2.
Implementation in Java
2.3.
Complexity Analysis
3.
Method 2: Recursion 
3.1.
Algorithm 
3.2.
Implementation in Java 
3.3.
Complexity Analysis
4.
Frequently Asked Questions 
4.1.
What is the time complexity of traversal operation?
4.2.
How is the linked list represented in memory?
4.3.
Why is a linked list stored in heap memory?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print Reverse of a Linked List Without Actually Reversing it

Author Alisha Chhabra
4 upvotes

Introduction to the problem statement 

Given a singly-linked list, print it in reverse order without actually reversing it. The only restriction is that you can’t reverse the original linked list. 

(Also see Data Structures)

Let us understand this problem with an example:-

Linked List 1->2->3->4->5

Output - 

5 -> 4 -> 3 -> 2 -> 1

According to the problem, we only need to print it in reverse order. 

To specify, you must begin printing the data from the tail and work your way up to the head of the list. 

To reverse the list itself, refer to this problem

Before you go further, we recommend you try to implement the problem on your own. 

Now that you have understood the problem let us switch to the possible methods to deal with the problem. 

 

Method 1: Using auxiliary space, stack 

As we all know, Stack is a powerful Data Structure that follows the LIFO( Last In First Out) principle to deal with the data. This signifies that the most recently added element will come out first. 

Illustration animation

SourceDevDojo

 

Similarly, extracting elements from the stack returns them in the reverse order of insertion. As a result of its LIFO trait, a stack can store elements in reverse order of insertion and hence can be utilized to address our problem.

The idea is to traverse the LinkedList from the head to the tail, pushing each traversed element onto the stack as you go. When the traversal is performed, the data from the linked list will be in reverse order in the stack. We can now extract the top element from the stack, print it, and then pop the elements one at a time, repeating the procedure until the stack is empty.

Now that you've devised a concept, let's look at its algorithm and implementation:

Algorithm 

  • Create an empty stack.

stack

  • Traverse the linked list and push each node onto the stack one by one. 

stack traversal insertion

  • After the traversal is performed, run a loop, in each iteration the topmost element must be printed and then popped out from the stack. Repeat this process until the stack becomes empty. 

illustration image

As a result, we’ve printed the reverse of a linked list without actually reversing it. 

Implementation in Java

// Java program to print reverse of a linked list using stack 
// Import all the packages
import java.util.*;
import java.io.*;

public class LinkedList{
    // head of a list
    Node head; 
    
    // linked list Node with two fields- data, next
    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }
    
    // function to print the reverse 
    public static void printReverse(Node head){
        // if the list is empty return to the call
        if(head == null){
            return;
        }
        // Create an empty stack
        Stack<Integer> sc = new Stack<>();
        // temp will point to the head 
        Node temp = head;
        // Run a loop until the temp points to null
        while(temp!=null){
            // one by one push each temp.data onto the stack
            sc.push(temp.data);
            // Update the temp to move ahead
            temp = temp.next;
        }
        // Run a loop until the stack becomes empty
        while(!sc.empty()){
            // get the top most element 
            int top = sc.peek();
            // print the top element
            System.out.print(top + "->");
            // delete the printed/top element
            sc.pop();
        }
        System.out.println("null");
    }
    // Utility function to print the linked list
    public static void print(Node head){
        Node temp = head;
        while(temp!=null){
            System.out.print(temp.data + "->");
            temp = temp.next;
        }
        System.out.println("null");
    }
    
    // Utility function to add the nodes in a list
    public void push(int new_data){
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    // main function 
    public static void main(String args[])
    {
        // Construct the linked list 1->2->3->4
        LinkedList list = new LinkedList();
        list.push(4);
        list.push(3);
        list.push(2);
        list.push(1);
        // Print the original list
        System.out.println("Given list: ");
        print(list.head);
        // print the list in reverse order
        System.out.println("Print reverse of a linked list in reverse order: ");
        printReverse(list.head);
    }
}
You can also try this code with Online Java Compiler
Run Code

Output

Given list: 
1->2->3->4->null
Print reverse of a linked list in reverse order: 
4->3->2->1->null

Complexity Analysis

Time Complexity: If we count the no. of operations we’ve performed through the program will be:

  1. Traversing of each node - O(N), where N is the number of total nodes in a list. 
  2. Pushing onto the stack - O(1), constant time. 
  3. Printing the stack - O(N), where N is the number of pushed nodes onto the stack. 

Hence, the time complexity to print the reverse of a linked list will be O(N) + O(N) +  O(1) =  o(2N+1) ~ O(N), where N is the total number of nodes in the list. 

Space Complexity: Since we are utilizing an additional data structure stack for storing the nodes, space complexity would be O(n), where n is the total number of pushed nodes, i.e., the total nodes in a given linked list. 

 

The approach we’ve discussed above is not optimized in the context of space. 

Can you think of a better approach for this? 

There is another approach that may not give us a better time complexity yet relieve us not to use auxiliary space. 

Let us discuss now:

Method 2: Recursion 

The idea is to traverse the linked list recursively. Since Recursion preserves a stack of calls during the execution, we would have a choice to print the nodes in reverse order. 

Let's have a look at the algorithm for this now:

Algorithm 

  • Make a function printReverse(), that will accept the head of the list as a parameter. 
  • Base case: If the linked list is empty, i.e., the head is null, simply return from the function. 
  • Make a recursive call by passing the next node of a list as an argument.
  • Print the node.data. 

We will have our linked list in reverse order. 

Consider the below representation to understand the algorithm:

linked list 1->2->3->4->5
illustration image algorithm

 

resultant list 5->4->3->2->!

Must Read Recursion in Data Structure

Implementation in Java 

// Java program to print reverse of a linked list using recursion
// Import all the packages
import java.util.*;
import java.io.*;

public class LinkedList{
    // head of a list
    Node head; 
    
    // linked list Node with two fields- data, next
    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }
    
    // function to print the reverse 
    public static void printReverse(Node head){
        // if the list is empty return to the call
        if(head == null){
            return;
        }
        // make a recursive call the next node
        printReverse(head.next);
        // print the node
        System.out.print(head.data + " ");
    }
    // Utility function to print the linked list
    public static void print(Node head){
        Node temp = head;
        while(temp!=null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
    
    // Utility function to add the nodes in a list
    public void push(int new_data){
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    // main function 
    public static void main(String args[])
    {
        // Construct the linked list 1->2->3->4
        LinkedList list = new LinkedList();
        list.push(4);
        list.push(3);
        list.push(2);
        list.push(1);
        // Print the original list
        System.out.println("Given list: ");
        print(list.head);
        // print the list in reverse order
        System.out.println("\nPrint reverse of a linked list in reverse order: ");
        printReverse(list.head);
    }
}
You can also try this code with Online Java Compiler
Run Code

Output

Given list: 
1 2 3 4
Print reverse of a linked list in reverse order: 
4 3 2 1 

Complexity Analysis

Time Complexity: Since we are traversing each node, the time taken to complete the traversal would be O(N), where N is the total number of nodes in a list.

Space Complexity: Since we’ve employed recursion which maintains a stack for each call, the space would be O(N), where N is the total number of recursive calls. 

Must Read  C Program to Reverse a Number

Frequently Asked Questions 

What is the time complexity of traversal operation?

The traversal operation visits each member of the data structure once, implying that the larger the number of elements/nodes, the longer it takes to traverse. 
For example, suppose you have two linked lists, one with five nodes and the other with ten. It will take less time to go through the first list than it would to go through the second, i.e., O(5) < O(10). 

How is the linked list represented in memory?

1Array-based static representation: A static representation of a single linked list maintains two arrays: data and links.
2Free pool of storage dynamic representation: A free storage pool is a collection of free memory spaces. When a node is needed during the creation of a linked list, the program sends a request to the memory to allocate the memory block.

Why is a linked list stored in heap memory?

The memory of a computer is split into heap and stack segments. The stack is smaller than the heap and has a set size. 
On the other hand, the linked list has the main advantage of dynamically extending itself as needed without worrying about memory usage. As a result, a heap is an optimal location for storing linked list-objects.

Conclusion

To cover up the session, we’ve looked at two approaches for printing a Linked List without actually reversing it. Approaches are many, but which are more optimized is needed. This was a fundamental question yet important for logic building and finalizing which method is more optimal. 

Similar problems you can look upon:


Furthermore, have a look at our top-notch courses just for you to have a bright and promising future. 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Keep coding and booming, Ninja!

Live masterclass