DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Print Linked List in Reverse Order using Recursion :

Source Code :

#include<stdio.h>
struct node *head=NULL;
//Pointer to store the staring node of the linked list
//Always stores the address location of first node
//Declared as global variable since it is accessed by multiple functions

struct node
{
    	//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
    	int data;
    	struct node *next;
};

void  print_reverse(struct node* p)
{
    	//Recursive function
    	//Function to print the linked list in reverse. i.e. from the last node
    	//Note that we are not reversing the linked list. We are just printing the list in reverse
	    if(p==NULL)
    	{
        		//Exit condition - It is most important thing to consider.Else the recursive function will be called infinitely
        		//The condition will be true for last node i.e the node with next pointer NULL
        		return;
    	}
    	print_reverse(p->next);
    	//Recursive funtion is called by passing address of next node
    	//p is current node and p->next is next node of node p

    	printf("\n%d ",p->data);
    	//Print the data from the node p
    	//This statement will be executed for the first time only when print_reverse(address of last node) of last node is called
    	//This statement will be executed for the first time only after the above if condition becomes true
}

void print()
{
    	//This funtion is used to print the data in each of the node in the linked list
    	//Process of moving from one node to another node is called as traversing
    	struct node *temp=head;
    	printf("\nList:");
    	while(temp!=NULL)
    {
        		printf("\n%d ",temp->data);
        		temp=temp->next;		
    	}
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	//Memory is allocated dynamically in heap and pointer "one" points to that allocated address
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));

    	head=one;
    	//The head points to node "one"

    	one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=3;
    	three->next=four;

    	four->data=4;
    	four->next=NULL;
    	//The last node points to NULL which means it is the end of linked list

    	//node one->node two->node three->four

    	printf("\nOriginal Linked List:");
    	print();
    	//Printing the linked list from first node to last node

    	printf("\nPrinting the linked list in reverse order:");
    	print_reverse(head);	
 	   //Printing the linked list from last node to first node

    	return 0;
}

Output :

Original Linked List:
List:
1
2
3
4

Printing the linked list in reverse order:
4
3
2
1