Inserting a node by using recursive programs

A linked list is a recursive data structure. A recursive data structure is a data structure that has the same form regardless of the size of the data. You can easily write recursive programs for such data structures.

# include <stdio.h>
# include <stdlib.h>
struct node 
{
	int data;
	struct node *link;
};
struct node *insert(struct node *p, int n) 
{
	struct node *temp;
	if (p == NULL) 
	{
		p = (struct node *) malloc(sizeof(struct node));
		if (p == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		p->data = n;
		p->link = NULL;
	} else
		p->link = insert(p->link, n);/* the while loop replaced by
		 recursive call */
	return (p);
}
void printlist(struct node *p) 
{
	printf("The data values in the list are\n");
	while (p != NULL) 
	{
		printf("%d\t", p->data);
		p = p->link;
	}
}
int main() 
{
	int n;
	int x;
	struct node *start = NULL;
	printf("Enter the nodes to be created \n");
	scanf("%d", &n);
	while (n-- > 0 )
	{
		printf("Enter the data values to be placed in a node\n");
		scanf("%d", &x);
		start = insert(start, x);
	}
	printf("The created list is\n");
	printlist(start);
	getchar();
	return 0;
}

Explanation

1. This recursive version also uses a strategy of inserting a node in an existing list to create the list.
2. An insert function is used to create the list. The insert function takes a pointer to an existing list as the first parameter, and a data value with which the new node is to be created as the second parameter. It creates the new node by using the data value, then appends it to the end of the list. It then returns a pointer to the first node of the list.
3. Initially, the list is empty, so the pointer to the starting node is NULL. Therefore, when insert is called the first time, the new node created by the insert function becomes the start node.
4. Subsequently, the insert function traverses the list by recursively calling itself.
5. The recursion terminates when it creates a new node with the supplied data value and appends it to the end of the list.

Points to Remember

1. A linked list has a recursive data structure.
2. Writing recursive programs for such structures is programmatically convenient.