# 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

N : 8
```

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) {
printf("\n%d Found\n", num);
return;
}
}
}
```

```#include <stdio.h>
#include <stdlib.h>

/* A structure of linked list node */
struct node {
int data;
struct node *next;

void initialize(){
}

/*
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  */
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) {
printf("\n%d Found\n", num);
return;
}
}
}

/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
initialize();
insert(8);
insert(3);
insert(2);
insert(7);
insert(9);

return 0;
}
```
Output
```Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9

9-->7-->2-->3-->8
7 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.
• 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;

void initialize(){
}

/*
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  */
printf("Inserted Element : %d\n", num);
}

/* Searches an element in Linked List using recursion */
struct node* search(struct node *head, int num) {
return NULL;
}

printf("\n%d Found\n", num);
} else {
}
}

/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
initialize();
insert(8);
insert(3);
insert(2);
insert(7);
insert(9);

return 0;
}
```
Output
```Inserted Element : 12
Inserted Element : 3
Inserted Element : 2
Inserted Element : 6
Inserted Element : 9