# Searching in a Linked List | Linked List Operations

Searching an element in a given linked list will happen sequentially starting from the head node of the list until the element has been found.

Searching in Linked List is a very basic operation and this operation is used to perform other important operations like

### Searching an element (Iterative approach)

1) Initialize a node pointer, temp = head
2) Do following while temp is not NULL
• temp->data is equal to the data being searched, return true.
• temp = temp->next
3) Return false
Now, let us see a program to search element in a linked list using the iterative approach.

## Iterative C Program to search for an element in the Linked List

`#include <stdio.h>#include <stdlib.h>// Creating node with data and a pointerstruct node {int data;struct node *next;}*head;void createList(int n);void search_element(int data);void displayList();int main(){int n, data, element;printf("\nEnter the total number of nodes: ");scanf("%d", &n);createList(n);printf("\nThe List is \n");displayList();printf("\nEnter the element to be searched in the list : "); // value of the element to be searched in the listscanf("%d",&element);search_element(element);return 0;}void createList(int n){struct node *newNode, *temp;int data, i;head = (struct node *)malloc(sizeof(struct node));// When the list is emptyif(head == NULL){printf("Unable to allocate memory.");}else{printf("\nEnter the data of node 1: ");scanf("%d", &data);head->data = data;head->next = NULL;temp = head;for(i=2; i<=n; i++){newNode = (struct node *)malloc(sizeof(struct node));if(newNode == NULL){printf("Unable to allocate memory.");break;}else{printf("\nEnter the data of node %d: ", i);scanf("%d", &data);newNode->data = data;newNode->next = NULL;temp->next = newNode;temp = temp->next;}}}}void search_element(int data){int count = 0;struct node* temp;temp = head;while(temp != NULL) // Start traversing from head node{if(temp -> data == data){printf("\nElement found at position %d",count);break;}else{count = count + 1;temp = temp -> next;}}printf("\n Element %d is not found in the list\n",data);}void displayList(){struct node *temp;if(head == NULL){printf("List is empty.");}else{temp = head;while(temp != NULL){printf("%d\t", temp->data);temp = temp->next;}printf("\n");}}`

OUTPUT

Time Complexity : O(n)

Space Complexity : O(1)

### Searching an element (Recursive approach)

1) If head is NULL, return false.
2) If head's data is same as the data to be searched, return true;
3) Else return search(head->next, search_data)

Now, let us see a program to search element in a linked list using iterative approach.

## Recursive C program to search for an element in a linked list

`#include <stdio.h>#include <stdlib.h>// Creating node with data and a pointerstruct node {int data;struct node *next;}*head;void createList(int n){struct node *newNode, *temp;int data, i;head = (struct node *)malloc(sizeof(struct node));// When the list is emptyif(head == NULL){printf("Unable to allocate memory.");}else{printf("\nEnter the data of node 1: ");scanf("%d", &data);head->data = data;head->next = NULL;temp = head;for(i=2; i<=n; i++){newNode = (struct node *)malloc(sizeof(struct node));if(newNode == NULL){printf("Unable to allocate memory.");break;}else{printf("\nEnter the data of node %d: ", i);scanf("%d", &data);newNode->data = data;newNode->next = NULL;temp->next = newNode;temp = temp->next;}}}}int search_element(int search_data){// Base caseif (head == NULL)return 0;// If key is present in current node, return trueif (head->data == search_data){return 1;}// Recur for remaining listhead = head -> next;return search_element(search_data);}void displayList(){struct node *temp;if(head == NULL){printf("List is empty.");}else{temp = head;// Print the listwhile(temp != NULL){printf("%d\t", temp->data);temp = temp->next;}printf("\n");}} int main(){int n, data, element;printf("\nEnter the total number of nodes: ");scanf("%d", &n);createList(n);printf("\nThe List is \n");displayList();printf("\nEnter the element to be searched in the list : "); // value of the element to be searched in the listscanf("%d",&element);int status = search_element(element);if(status == 1){printf("Element is found in the linked list\n");}elseprintf("\nElement is not found in the linked list\n");return 0;}`

OUTPUT

Time Complexity : O(n)

Space Complexity : O(n), since extra space is used in stack to store activation records of function getting called recursively.

### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`