Program to Search an Element in Linked List using Loop and Recursion

• Write a C program to search an element in a linked list using loop.
• How to find an element in linked list using recursion.

To search an element in a linked list, we can either use iteration or recursion. We have to write a function in C which takes head node of a linked list and number N as input and prints whether N is present in linked list or not. For Example :

Linked List : 4-->9-->10-->2-->5-->NULL
N : 5
5 Found 

Linked List : 4-->9-->10-->2-->5-->NULL
N : 8
8 Not Found

---

Method 1 : Using Iteration

C program to search an element in linked list using loop

Algorithm to search an element in a linked list
Let "head" be the head pointer of given linked list and N be the element we are searching for.

• Using a while loop, traverse linked list until (head != NULL).
• For every node check, whether head->data is equal to N. If true then return 1 else move head pointer to next node(head = head->next;) and continue.
• Return 0;

Time Complexity : O(n), where n is the number of nodes in linked list.

In this program, we will use a user defined function "search" which takes head pointer of a linked list and an integer num as input and print's whether num is present in linked list or not.

void search(struct node *head, int num) {
    while (head != NULL) {
        if (head->data == num){
            printf("\n%d Found\n", num);
            return;
        }
        head = head->next;
    }
    printf("\n%d Not Found\n", num);
}

---

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

/* Searches an element in Linked List by 
linearly traversing from head to tail */
void search(struct node *head, int num) {
    while (head != NULL) {
        if (head->data == num){
            printf("\n%d Found\n", num);
            return;
        }
        head = head->next;
    }
    printf("\n%d Not Found\n", num);
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);  
    insert(3); 
    insert(2); 
    insert(7);
    insert(9);
    
    printf("\nLinked List\n");
    printLinkedList(head);

    search(head, 7);
    search(head, 5);
    
    return 0;
}

Output

Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9

Linked List
9-->7-->2-->3-->8
7 Found

5 Not Found

---

Method 2 : Using Recursion

C program to search an element in linked list using recursion

Recursive Algorithm to find an element in a linked list
Let "head" be the head pointer of given linked list and N be the element we are searching for.

• If head is equal to NULL, print "N not found".
• Check if current node's data is equal to N(head->data == N). If equal then print "N Found".
• Else continue recursive search as search(head->next);

---

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

/* Searches an element in Linked List using recursion */
struct node* search(struct node *head, int num) {
    if(head == NULL){
        printf("\n%d Not Found\n", num);
        return NULL;
    }
    
    if(head->data == num) {
        printf("\n%d Found\n", num);
        return head;
    } else {
        return search(head->next, num);
    }
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);  
    insert(3); 
    insert(2); 
    insert(7);
    insert(9);
    
    printf("\nLinked List\n");
    printLinkedList(head);

    search(head, 1);
    search(head, 3);
    
    return 0;
}

Output

Inserted Element : 12
Inserted Element : 3
Inserted Element : 2
Inserted Element : 6
Inserted Element : 9

Linked List
9-->6-->2-->3-->12
1 Not Found
3 Found