- 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