Bdtjtk

I was searching on how can I print a reverse of linked list and I found this piece of code

/* 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);

}

The problem is that I do not understand the part where it reaches the last pointer which points to NULL and how it comes back one by one and prints the linked list in reverse order.

Is the return statement what makes it go step by step back? Or something else? Please help because I do not understand.

This is a recursive function. Recursive functions work by pushing variables onto the execution stack. The execution order pops off the stack in reverse order from the order it was pushed on the stack. This means that the last execution prints first, then the one previous to that, and so forth until all executions of printReverse print their values.

This is a recursive function; that is to say, it calls itself.

Let's use the sequence example as your example data:

When you first run the function, it's pointing at the head, and the head is the item containing the data e. It has a next property, which is the item containing the data x. Therefore, head == NULL evaluates False and the if statement doesn't fire.

The function then calls a second copy of itself, pointing to the next item in the list - the item containing x. This has a next property, which is the item containing a. The function then calls a third copy of itself with this item, and so on and so forth until it hits the final e, and calls a copy of itself with the next property of that item - that is to say, it calls itself with NULL as the input.

This copy of the function then returns due to the if statement- crucially, it returns to the function that called it, in this case the copy of itself the level above. This copy then carries on where it left off, executing printf("%d ", head->data); - in this case, it prints an e. Then it falls out of the body of the function and so returns to the function that called it. This copy of the function will have a head->data value of l, and this will print as above. As such, it then runs through back up the chain until it gets to the original function call, prints the first e, and then returns to the function that called it.

Hope this makes sense, I know it's not the best or most elegant explanation of recursion but there's a lot of material out there if this is confusing explaining exactly how recursion works and how useful it can be!

The thing that makes it go in reverse is to have the printf() call after the recursive call to itself.

You can try interchanging the two calls as in

void printNormal(struct node* head)

{

    // Base case  

    if (head == NULL)

       return;



    // Before all, we print this node info.

    printf("%d  ", head->data);



    // print the rest of the list after this node

    printReverse(head->next);



}

And you'll get the forward printing of the list.

The mission of the so commented Base case is to avoid infinite recursion. The end of the list is special, we can do the check on entering the printReverse() function, so we can deal with the special case of an empty list, or we have to do it at each call (then we should put a check before calling the function inside it, and in the code that calls the recursive function (better to put it at the beginning).

As others have already explained the recursive version. I suggest you to have a look at this iterative version of printing linked list in reverse order. This is more easy to understand and implement as compared to recursive version, however it increases time complexity.

    // To ease testing of code here linked list is created randomly of given size.

    #include<stdio.h>

    #include<cstdlib>

    #include<time.h>

    #define size 10 //Size of list

    struct node

    {

          int info;

          struct node * next;

    };

    typedef struct node* Node;       

    Node start;

    int main()

    {

       int i;

       srand(time(NULL));

       for(i=0;i<size;i++)

       {

          Node ptr;

          ptr=(Node)malloc(sizeof(node));

          ptr->info=rand()%100; //random list is created of given size.

          ptr->next=NULL;

          if(start==NULL)

              start=ptr;

          else

          {

               ptr->next=start;

               start=ptr;

          }

    }

    printf(" Traversal of Linked List in forward direction -n");

    Node temp=start;

    while(temp!=NULL)

    {

        printf(" %d ",temp->info);

        temp=temp->next;

    }

    printf("n Traversal of Linked List in backward direction -n");

    Node ptr=NULL;

    while(ptr!=start)

    {

        temp=start;

        while(temp->next!=ptr)

        temp=temp->next;

        printf(" %d ",temp->info);

        ptr=temp;

    }

       return 0;

    }

For more details visit-
https://github.com/SahdevKansal02/Data-Structures-And-Algorithms.git

Jim Rodgers hits the nail on the head. However, you could make life very easy for yourself by having a doubly linked list.

So for example your entry (node) has both a previous and next member pointing to the previous entry and next entry respectively. Then you don't need more "obfuscated" code than necessary.