Home »
C/C++ Data Structure Programs
C program to traverse the linked list using recursion
Here, we are going to learn how to traverse the linked list using recursion using C program?
Submitted by Nidhi, on August 19, 2021
Problem Solution:
Create a linked list, traverse, and print the linked list.
Program:
The source code to traverse the linked list using recursion is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.
// C program to traverse the linked list
// using the recursion
#include <stdio.h>
#include <stdlib.h>
//Self referential structure to create node.
typedef struct tmp {
int item;
struct tmp* next;
} Node;
//structure for create linked list.
typedef struct
{
Node* head;
Node* tail;
} List;
//Initialize List
void initList(List* lp)
{
lp->head = NULL;
lp->tail = NULL;
}
//Create node and return reference of it.
Node* createNode(int item)
{
Node* nNode;
nNode = (Node*)malloc(sizeof(Node));
nNode->item = item;
nNode->next = NULL;
return nNode;
}
//Add new item at the end of list.
void addAtTail(List* lp, int item)
{
Node* node;
node = createNode(item);
//if list is empty.
if (lp->head == NULL) {
lp->head = node;
lp->tail = node;
}
else {
lp->tail->next = node;
lp->tail = lp->tail->next;
}
}
//Add new item at begning of the list.
void addAtHead(List* lp, int item)
{
Node* node;
node = createNode(item);
//if list is empty.
if (lp->head == NULL) {
lp->head = node;
lp->tail = node;
}
else {
node->next = lp->head;
lp->head = node;
}
}
void TraverseList(Node* node)
{
if (node == NULL)
return;
printf("| %05d |", node->item);
if (node->next != NULL)
printf("--->");
TraverseList(node->next);
}
//Main function to execute program.
int main()
{
List* lp;
lp = (List*)malloc(sizeof(List));
initList(lp);
addAtTail(lp, 100);
addAtTail(lp, 200);
addAtHead(lp, 300);
addAtHead(lp, 400);
addAtHead(lp, 500);
printf("List:\n");
TraverseList(lp->head);
printf("\n");
return 0;
}
Output:
List:
| 00500 |--->| 00400 |--->| 00300 |--->| 00100 |--->| 00200 |
Explanation:
Here, we created a self-referential structure to implement a linked list., a function to add a node at the start and end of the list, a recursive function TraverseList() to traverse and print linked list items.
In the main() function, we created the linked list and traversed the linked list items and printed them.