facebook like button

23 September, 2011

program to print a linked list in reverse order

The need: 
     This program is a program to prints a linked list in reverse order without actually reversing it (For reversing a given linked list have a look on program78 of this blog). This program is written to show how recursion becomes more useful. First it asks user to enter numbers to be entered into linked list then creates a linked list, prints it in same as given and reversed order.
The code: 
---------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
typedef struct linked_list
{
    int item;
    struct linked_list *next;
}node;

node *create_list();
void print_list(node *);
void print_list_in_reverse(node *);

int main()
{
    node *head=NULL;
    printf("This program creates a linked list and then prints it first in given order and then in reverse\n");
    printf("create a list by entering elements press -999 to end\n");
    head=create_list();
    printf("\nThe list is\n");
    print_list(head);
    printf("\nThe list in reverse order is");
    print_list_in_reverse(head);
    printf("\n");
    return 0;
}

node *create_list()
{
    int x;
    node *temp=NULL;
    scanf("%d",&x);
    if(x!=-999)
    {
        temp=(node*)malloc(sizeof(node));
        temp->item=x;
        temp->next=NULL;
        temp->next=create_list();
    }
    return temp;
}
void print_list(node *p)
{
    if(p)
    {
        printf("%d ",p->item);
        print_list(p->next);
    }
    else
    printf("\n");
}

void print_list_in_reverse(node *p)
{
    if(p)
    {
        print_list_in_reverse(p->next);
        printf("%d ",p->item);
    }
    else
    printf("\n");
}
---------------------------------------------------------
The need:
   The approach is nothing but basics of recursion.
If we say the recursion in create_list function in normal English, we'll say "It will take a number form user if it is not -999, a new node is created, data is filled in it and address of this node is returned else NULL is returned." because temp is initialised to NULL each time in the starting of function.
If we say the recursion in print_list function in normal English, we'll say "It will print the data of a node and then go for doing the same to the next node after that if present".
If we say the recursion in print_list_in_reverse function in normal English, we'll say "It will print the data of a node when all the node after that are printed or if there is no node after that node".
 
Remarks:
1. We can print linked list as it is (in the given order) without using extra storage or extra thinking. We can just use loops but if we are asked to write a program to print the linked list without actually reversing it, we can not do it by just using loops. What we can do is next point.
2. For that we have to create a stack and push addresses of all the elements of linked list on it starting from head to end. Then pop addresses one by one and print the corresponding data. This requires extra storage and extra thinking.
3. So in this program recursion is the way to do the same without extra thinking and without explicitly using extra memory and functions.
4. I wrote explicitly with stress because recursion actually uses its own stack (System stack). Now I am not going into these details.

No comments:

Post a Comment

feel free to ask your doubts... if any
you can post your doubts on
www.facebook.com/programsimply