Recursion On Linked List

Recursive Operations On Linked List:

• Insertion in linked list using recursion
• Deletion linked list using recursion
• Copy linked list using recursion
• Count nodes in linked list using recursion
  
  
  Example Program To Perform Recursive Operations On Linked List(in C):

  ---

  
  
    #include<stdio.h>
    #include<stdlib.h>
  
    struct node {
          int data;
          struct node *next;
    };
  
    struct node *head1, *head2, *head3;
    int nCount = 0;
  
    /*
     * creates node and fill the given data
     */
    struct node * createNode(int data) {
          struct node *ptr = (struct node *) malloc(sizeof (struct node));
          ptr->data = data;
          ptr->next = NULL;
          return ptr;
    }
  
    /* insertion operation - using recursion */
    void insert(struct node ** myNode, int data) {
          if (*myNode) {
                  insert(&(*myNode)->next, data);
          } else {
                  *myNode = createNode(data);
          }
          return;
    }
  
    /* copy contents from list1 to list 2 - using recursion*/
    void copyList(struct node *list1, struct node **list2) {
          if (list1) {
                  *list2 = createNode(list1->data);
                  copyList(list1->next, &(*list2)->next);
          }
          return;
    }
  
    /* compare contenst of list 1 & list 2 - using recursion */
    int compareList(struct node *list1, struct node *list2) {
          if (!list1 && !list2) {
                  printf("Both First & Second List are same!!\n");
                  return (1);
          }
  
          if (!list1 || !list2 || (list1->data != list2->data)) {
                  printf("Both Lists are not equal!!\n");
                  return 0;
          } else {
                  return (compareList(list1->next, list2->next));
          }
  
    }
  
    /* delete the given list using recursion */
    struct node * deleteList(struct node *ptr) {
          struct node *temp;
          if (ptr){
                  temp = ptr->next;
                  free(ptr);
                  deleteList(temp);
          }
          return NULL;
    }
  
    /* no of nodes in the given list */
    int nodeCount(struct node *ptr) {
          if (ptr) {
                  nCount++;
                  nodeCount(ptr->next);
          }
          return;
    }
  
  
  
    /* travese the whole list and print the contents of each node */

    int walkList(struct node *ptr) {

          int i = 0;

          while (ptr) {

                  printf("%d ", ptr->data);

                  ptr = ptr->next;

                  i++;

          }

          return (i);

    }
  
  
    int main (int argc, char *argv[]) {

          int data, i, n;

          FILE *fp1;

          fp1 = fopen(argv[1], "r");

  
  

          if (!fp1) {

                  printf("Unable to open file\n");

                  exit(0);

          }

  
  

          /* read data from the input file */

          while (fscanf(fp1, "%d", &data) != EOF) {

                  insert(&head1, data);

          }

  
  

          printf("\nData in First Linked List:\n");

          n = walkList(head1);

          printf("\nNo of elements in linked list: %d\n", n);

          printf("\nCopied data from linked list 1 to 2!!");

          copyList(head1, &head2);

          printf("\n\nData in Second Linked List:\n");

          n = walkList(head2);

          nodeCount(head2);

          printf("\nNo of elements in linked list: %d\n\n", nCount);

          compareList(head1, head2);

          printf("\n");

          head1 = deleteList(head1);

          head2 = deleteList(head2);

          return 0;

    }
  
  
  
    Output: (Recursion in Singly Linked List - Example Program in C)
  
    1 3 5 7 9 11 13 15
  
    Data in First Linked List:
    1 3 5 7 9 11 13 15
    No of elements in linked list: 8
   
    Copied data from linked list 1 to 2!!
  
    Data in Second Linked List:
    1 3 5 7 9 11 13 15
    No of elements in linked list: 8
  
    Both First & Second List are same!!