Reverse Traversal (Displaying in Reverse)

A singly linked list (SLL) only has next, so you cannot walk backward in one forward pass. To print values in reverse order without reversing the list structure, common options are: recurse first and print on the way back (implicit call stack), or push node pointers onto an explicit stack then pop. Both are O(n) time; recursion uses O(n) call-stack space; the array stack uses O(n) extra space for pointers. (A doubly linked list could use prev instead.)

1) Recursion — print after visiting next

Recurse to the end of the list first; print when unwinding. Output order becomes reverse of the forward chain.

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

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

void print_reverse_recursive(struct Node *p)
{
    if (p == NULL)
        return;
    print_reverse_recursive(p->next);
    printf("%d ", p->data);
}

int main(void)
{
    struct Node *n1 = malloc(sizeof(struct Node));
    struct Node *n2 = malloc(sizeof(struct Node));
    struct Node *n3 = malloc(sizeof(struct Node));
    if (!n1 || !n2 || !n3) return 1;

    n1->data = 10; n1->next = n2;
    n2->data = 20; n2->next = n3;
    n3->data = 30; n3->next = NULL;

    print_reverse_recursive(n1);   /* output: 30 20 10 */
    printf("\n");

    free(n1); free(n2); free(n3);
    return 0;
}

Program output

Reverse order on one line, then newline from main:

Recursive call stack (post-order: recurse first, print on unwind)

Complete call stack trace (with unwinding)

Memory layout (same three-node list)

Visual call tree (post-order printing)

Timing: when prints occur

Forward vs reverse recursive printing

2) Explicit stack — array of struct Node *

First pass: count nodes (or push in one pass if you pre-allocate). Second pass: fill a stack array with pointers in forward order, then pop from the top while printing. Here we count, then malloc an array of that many pointers.

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

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

void print_reverse_explicit_stack(struct Node *head)
{
    int n = 0;
    struct Node *t;
    for (t = head; t != NULL; t = t->next)
        n++;
    if (n == 0)
        return;

    struct Node **stack = malloc((size_t)n * sizeof(struct Node *));
    if (stack == NULL)
        return;

    int top = 0;
    for (t = head; t != NULL; t = t->next)
        stack[top++] = t;

    while (top > 0)
        printf("%d ", stack[--top]->data);
    printf("\n");

    free(stack);
}

int main(void)
{
    struct Node *n1 = malloc(sizeof(struct Node));
    struct Node *n2 = malloc(sizeof(struct Node));
    struct Node *n3 = malloc(sizeof(struct Node));
    if (!n1 || !n2 || !n3) return 1;

    n1->data = 10; n1->next = n2;
    n2->data = 20; n2->next = n3;
    n3->data = 30; n3->next = NULL;

    print_reverse_explicit_stack(n1);   /* output: 30 20 10 */

    free(n1); free(n2); free(n3);
    return 0;
}

Program output

Same reverse line as the recursive version, then newline from printf("\n") inside the function:

Algorithm phases

Phase 1: counting nodes

Result: n = 3 nodes.

Phase 2: memory allocation

Phase 3: pushing node pointers

After the push loop, top == 3 (number of elements stored). The pop loop uses while (top > 0) with stack[--top].

Phase 4: popping and printing

Then printf("\n") appends the newline. List nodes are still freed later in main.

Memory visualization

List nodes (heap)

Stack array after push phase (heap)

Stack pointer movement

Initial:  top = 0     [   ?   ,   ?   ,   ?   ]
Push n1:  top = 1     [  n1   ,   ?   ,   ?   ]
Push n2:  top = 2     [  n1   ,  n2   ,   ?   ]
Push n3:  top = 3     [  n1   ,  n2   ,  n3   ]
Pop:      top = 2     print stack[2] → 30
Pop:      top = 1     print stack[1] → 20
Pop:      top = 0     print stack[0] → 10

Complexity

Explicit stack vs recursion

The stack array holds pointers to existing nodes; it does not copy the list. If you cannot afford two passes, you can push pointers in a single traversal into a dynamically grown buffer, or use a linked stack—same idea.

Comparison: Reverse linked list vs tree post-order traversal

The fundamental similarity

Both follow the “process after children” pattern:

Key similarities

Practical examples where both are useful

Printing a linked list in reverse order is essentially a special case of post-order traversal where:

• Each node has exactly one “child” (next pointer).
• The post action is printing the node.
• The linear structure simplifies to: go to the end, then print while coming back.