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.