Print Reverse of a Linked List Without Actually Reversing in C

Last Updated on July 4, 2023 by Mayank Dham

Linked lists are fundamental data structures used in computer science and programming. They provide a flexible way to store and manipulate collections of data. One common task when working with linked lists is to print the elements in reverse order. While reversing the linked list itself is a straightforward solution, it involves modifying the original structure, which may not always be desirable or efficient.

In this article, we explore an alternative approach to print the reverse of a linked list in C without actually reversing the list itself. We will leverage the power of stacks, a popular data structure that follows the Last-In-First-Out (LIFO) principle. By utilizing a stack, we can achieve the desired outcome efficiently while preserving the original order of the linked list.

How To Print Reverse of a Linked List without Actually Reversing it in C?

Let us understand this problem with an example:
Let’s say we have the given linked list as,

According to the problem we need to print it in reverse order. Reverse order means we have to print the values of nodes from right to left.
So the desired output for this linked list will be 5 4 3 2 1.
We need to do this without reversing the given linked list.
Hope that you have understood the problem. Now try to come up with an approach.
If we were allowed to reverse the linked list, then it would be simple. But here we aren’t allowed to do so. So, try to think how we should approach this problem?

Approach 1: Print Reverse of a Linked List Without Actually Reversing in C Using Stack

Let’s see how a stack works.
The LIFO (last in, first out) principle is used. This indicates that the element that was most recently inserted will appear first. Likewise, if we take pieces out of the stack, we will receive them in the opposite order from when they were inserted. This is just what we require.
Therefore, a stack can be utilized to solve our problem because of its LIFO attribute, which allows it to store elements in the reverse order of their entry.
Simply go over the linked list and insert each node’s value into the stack one at a time. The linked list’s data would be in reverse order in the stack once the traversal is finished. We can now take each element out of the stack one at a time, print it, and then remove it by popping it.

Algorithm

1. Make an empty stack
2. Push the value in the nodes of the linked list to the stack as you traverse it.
3. After iteration, remove each piece from the stack one at a time and print it.
4. We would flip the order of printing our linked list.

Stack Code Implementation

#include <stdio.h>
#include <stdlib.h>

// Node definition
struct Node {
    int data;
    struct Node* next;
};

// Push operation for stack
void push(struct Node** top, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *top;
    *top = newNode;
}

// Pop operation for stack
int pop(struct Node** top) {
    if (*top == NULL) {
        printf("Stack is empty.\n");
        return -1;
    }
    struct Node* temp = *top;
    int data = temp->data;
    *top = (*top)->next;
    free(temp);
    return data;
}

// Printing the reverse of linked list without reversing the list
void printReverse(struct Node* head) {
    struct Node* temp = head;
    struct Node* stack = NULL;

    while (temp != NULL) {
        push(&stack, temp->data);
        temp = temp->next;
    }

    while (stack != NULL) {
        printf("%d ", pop(&stack));
    }
}

// Test program
int main() {
    // Create a sample linked list
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;

    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    second->data = 2;

    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    third->data = 3;

    head->next = second;
    second->next = third;
    third->next = NULL;

    // Print the reverse of the linked list
    printf("Reverse of the linked list: ");
    printReverse(head);

    // Clean up the linked list
    free(head);
    free(second);
    free(third);

    return 0;
}

Output

Reverse of the linked list: 3 2 1 

Time complexity: O(N), as we are doing a complete traversal of the linked list.
Space complexity: O(N), as we are using a stack to store all the nodes.
Where N is the number of nodes in the linked list.

The above algorithm does the work, but it requires extra space. So, can we think of some way to avoid using extra space?

Approach 2 Print Reverse of a Linked List Without Actually Reversing in C Using Recursion

Recursively traversing a linked list gives us the option of printing a node either before or after the other nodes have been traversed. We could accomplish our goal of printing the linked list in reverse order if we print a node after exploring the remaining nodes.

Algorithm

1. Base case: Simply return from the function if the linked list is empty.
2. Before printing, it calls the same method recursively for the following node for the current node. With this, all nodes after the current node will be printed.
3. We now simply output the value of the active node.

We will have our linked list printed in reverse order.

Code Implementation

#include<stdio.h>
#include<stdlib.h>
  
/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};
  
/* Function to reverse the linked list */
void printReverse(struct Node* head)
{
    // Base case 
    if (head == NULL)
       return;
 
    // print the list after head node
    printReverse(head->next);
 
    // After everything else is printed, print head
    printf("%d  ", head->data);
}
  
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
  changes the head */
void push(struct Node** head_ref, char new_data)
{
    /* allocate node */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
  
    /* put in the data  */
    new_node->data  = new_data;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);  
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
  
/* Driver program to test above function*/
int main()
{
    // Let us create linked list 1->2->3->4
    struct Node* head = NULL;   
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
   
    printReverse(head);
    return 0;
}

Output

4  3  2  1

Time Complexity:
The time complexity of this approach is O(n), where n is the number of nodes in the linked list. This is because the recursive function visits each node once, performing a constant amount of work (printing the node value) at each step.

Space Complexity:
The space complexity of the recursion approach is O(n) as well. Each recursive call adds a new stack frame to the call stack, consuming space. Since there can be at most n recursive calls (equal to the number of nodes in the linked list), the space required by the call stack grows linearly with the size of the linked list.

Conclusion
In conclusion, we have explored two different approaches for printing the reverse of a linked list without actually reversing it in C: the stack-based approach and the recursion approach. Each approach offers its own advantages and considerations.

The stack-based approach provides an efficient solution by utilizing a stack data structure. It involves traversing the linked list and pushing each element onto the stack. Later, by popping and printing the elements from the stack, we achieve the reverse order. This approach preserves the original linked list structure, requires only additional memory for the stack, and offers a straightforward implementation.

On the other hand, the recursion approach offers an elegant solution by leveraging the recursive nature of the problem. It uses a recursive function that traverses the linked list until it reaches the end. Then, during the backtracking phase, it prints the elements in reverse order. This approach also preserves the original linked list structure and requires minimal additional memory. However, it may have a higher space overhead due to the function call stack.

FAQ

Q1: What is the purpose of printing the reverse of a linked list without actually reversing it?
The task of printing the reverse of a linked list without reversing it is often required to preserve the original order of the linked list while still achieving the desired output. It can be useful in situations where modifying the original linked list structure is not allowed or when memory constraints are a concern.

Q2: What are the two different approaches to printing the reverse of a linked list without reversing it?
The two common approaches are the stack-based approach and the recursion approach.

Q3: How does the stack-based approach work?
In the stack-based approach, we traverse the linked list and push each element onto a stack. After traversing the entire list, we pop and print the elements from the stack, resulting in the reverse order. This approach preserves the original linked list structure and uses a stack data structure to temporarily store the elements.

Q4: What are the advantages of the stack-based approach?
The stack-based approach allows us to print the reverse order of the linked list without modifying the original structure. It requires only additional memory for the stack, offers a straightforward implementation, and has a time and space complexity of O(n), where n is the number of nodes in the linked list.

Q5: How does the recursion approach work?
In the recursion approach, we use a recursive function to traverse the linked list. When reaching the end of the list, during the backtracking phase, we print the elements in reverse order. This approach also preserves the original linked list structure and has a space complexity of O(n), but it may have a higher space overhead due to the function call stack.

Q6: What are the advantages of the recursion approach?
The recursion approach provides an elegant solution by leveraging the recursive nature of the problem. It requires minimal additional memory, has a concise implementation, and also has a time complexity of O(n), making it an efficient choice.

Q7: How do I choose between the stack-based and recursion approaches?
The choice depends on the specific requirements of your problem and the trade-offs involved. If minimizing space usage is a concern, the stack-based approach may be more suitable. However, if you prefer a concise and intuitive solution, the recursion approach can be a good option.