Recursive insertion and traversal linked list

The task is to implement a singly linked list with two core functionalities using recursion:

Insertion: Insert a new node at the end of the linked list.

Traversal: Traverse the linked list and print the data stored in each node.

Example :

Input: Values to be inserted = 1, 2, 3, 4, 5
Output: 1 -> 2 -> 3 -> 4-> 5 -> NULL
Explanation : We have to first recursively insert each node with the given input value and then print the linked list recursively

Input: Values to be inserted = 7, 8, 4, 11, 44, 6
Output: 7 -> 8 -> 4 -> 11 -> 44 -> 6 -> NULL

Approach :

Define a Node class/struct with data and a reference to the next node. Implement a recursive function to insert a new node at the end of the list. Finally, use a recursive traversal function to print the data of each node in the list.

Follow the steps below to solve the problem:

1. Insert a Node: Write a function that adds a new node to the end of the list. If the list is empty, this new node becomes the first node. If the list already has nodes, the function will keep moving to the next node until it finds the last one, then adds the new node there.

2. Traverse the List: Write a function to go through each node in the list, starting from the first one. While traversing each node, it will print out the data stored in that node. This function will keep moving to the next node until it reaches the end of the list.

Below is the implementation of the above approach:

// C++ program to implement Recursive insertion and  // traversal in a linked list  #include <bits/stdc++.h> using namespace std; class Node { public:  int data;  Node* next;  Node(int new_data) {  data = new_data;  next = nullptr;  } }; // Function to insert a new node at the  // end of linked list using recursion. Node* insertEnd(Node* head, int data) {  // If linked list is empty, create a new node  if (head == nullptr)   return new Node(data);  // If we have not reached the end,   // keep traversing recursively  head->next = insertEnd(head->next, data);  return head; } // Function to traverse and print the linked list // starting from the head node, recursively void traverse(Node* head) {  if (head == nullptr)  return;  cout << head->data << " ";    // Recur for the remaining list  traverse(head->next); } int main() {    // Insert nodes with data 1, 2, 3, 4, 5  Node* head = nullptr;  head = insertEnd(head, 1);  head = insertEnd(head, 2);  head = insertEnd(head, 3);  head = insertEnd(head, 4);  head = insertEnd(head, 5);  traverse(head); } 

// C program to implement Recursive insertion and  // traversal in a linked list  #include <stdio.h> #include <stdlib.h> struct Node {  int data;  struct Node* next; }; struct Node* newNode(int new_data); // Function to insert a new node at the  // end of linked list using recursion. struct Node* insertEnd(struct Node* head, int data) {  // If linked list is empty, create a new node  if (head == NULL)   return newNode(data);  // If we have not reached the end,   // keep traversing recursively  head->next = insertEnd(head->next, data);  return head; } // Function to traverse and print the linked list // starting from the head node, recursively void traverse(struct Node* head) {  if (head == NULL) return;  printf("%d ", head->data);    // Recur for the remaining list  traverse(head->next); } struct Node* newNode(int new_data) {  struct Node* new_node =   (struct Node*)malloc(sizeof(struct Node));  new_node->data = new_data;  new_node->next = NULL;  return new_node; } int main() {    // Insert nodes with data 1, 2, 3, 4, 5  struct Node* head = NULL;  head = insertEnd(head, 1);  head = insertEnd(head, 2);  head = insertEnd(head, 3);  head = insertEnd(head, 4);  head = insertEnd(head, 5);  traverse(head);  return 0; } 

// Java program to implement Recursive insertion and  // traversal in a linked list  class Node {  int data;  Node next;  Node(int new_data) {  data = new_data;  next = null;  } } public class GfG {  // Function to insert a new node at the   // end of linked list using recursion.  static Node insertEnd(Node head, int data) {  // If linked list is empty, create a new node  if (head == null)   return new Node(data);  // If we have not reached the end  // keep traversing recursively  head.next = insertEnd(head.next, data);  return head;  }  // Function to traverse and print the linked list  // starting from the head node, recursively  static void traverse(Node head) {  if (head == null) return;    System.out.print(head.data + " ");  // Recur for the remaining list  traverse(head.next);  }    public static void main(String[] args) {    // Insert nodes with data 1, 2, 3, 4, 5  Node head = null;  head = insertEnd(head, 1);  head = insertEnd(head, 2);  head = insertEnd(head, 3);  head = insertEnd(head, 4);  head = insertEnd(head, 5);  traverse(head);  } } 

# Python program to implement Recursive insertion and  # traversal in a linked list  class Node: def __init__(self, new_data): self.data = new_data self.next = None # Function to insert a new node at the  # end of linked list using recursion. def insert_end(head, data): # If linked list is empty, create a new node if head is None: return Node(data) # If we have not reached the end, # keep traversing recursively head.next = insert_end(head.next, data) return head # Function to traverse and print the linked list # starting from the head node, recursively def traverse(head): if head is None: return print(head.data, end=" ") # Recur for the remaining list traverse(head.next) if __name__ == "__main__": # Insert nodes with data 1, 2, 3, 4, 5 head = None head = insert_end(head, 1) head = insert_end(head, 2) head = insert_end(head, 3) head = insert_end(head, 4) head = insert_end(head, 5) traverse(head) 

// C# program to implement Recursive insertion and  // traversal in a linked list  using System; class Node {  public int data;  public Node next;  public Node(int new_data) {  data = new_data;  next = null;  } } class GfG {  // Function to insert a new node at the   // end of linked list using recursion.  static Node InsertEnd(Node head, int data) {  // If linked list is empty, create a new node  if (head == null)   return new Node(data);  // If we have not reached the end,  // keep traversing recursively  head.next = InsertEnd(head.next, data);  return head;  }  // Function to traverse and print the linked list  // starting from the head node, recursively  static void Traverse(Node head) {  if (head == null)  return;  Console.Write(head.data + " ");  // Recur for the remaining list  Traverse(head.next);  }  static void Main(string[] args) {    // Insert nodes with data 1, 2, 3, 4, 5  Node head = null;  head = InsertEnd(head, 1);  head = InsertEnd(head, 2);  head = InsertEnd(head, 3);  head = InsertEnd(head, 4);  head = InsertEnd(head, 5);  Traverse(head);  } } 

// Javascript program to implement Recursive insertion and  // traversal in a linked list  class Node {  constructor(new_data) {  this.data = new_data;  this.next = null;  } } // Function to insert a new node at the  // end of linked list using recursion. function insertEnd(head, data) {  // If linked list is empty, create a new node  if (head === null)   return new Node(data);  // If we have not reached the end,  // keep traversing recursively  head.next = insertEnd(head.next, data);  return head; } // Function to traverse and print the linked list // starting from the head node, recursively function traverse(head) {  if (head === null)  return;  console.log(head.data + " ");  // Recur for the remaining list  traverse(head.next); } // Insert nodes with data 1, 2, 3, 4, 5 let head = null; head = insertEnd(head, 1); head = insertEnd(head, 2); head = insertEnd(head, 3); head = insertEnd(head, 4); head = insertEnd(head, 5); traverse(head); 

1 2 3 4 5 

Time Complexity: O(n), to traverse the linked list of size n
Auxiliary Space: O(n), for recursion call stack