Problem Statement: Search an element in a Linked List
i) Iterative solution
ii) Recursive solution
Iterative Solution
| 1) Initialize temp node to head 2) while temp is not NULL a) temp->data is equal to the key being searched return true. b) temp = temp->next 3) Return false |
/*C code to Search an element in a Linked List */
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *head = NULL;
NODE *newNode(int key)
{
NODE *temp = (NODE *)malloc(sizeof(NODE));
temp->data = key;
temp->next = NULL;
return temp;
}
void search(int key)
{
NODE *temp = head;
while (temp != NULL)
{
if (temp->data == key)
{
printf("%d is present in the Linked List!", key);
return;
}
temp = temp->next;
}
printf("%d is not present in the Linked List!", key);
}
void printList()
{
NODE *temp = head;
if (temp == NULL)
{
printf("List is empty!\n");
return;
}
printf("Linked List is\t");
while (temp != NULL)
{
printf("%d--> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main()
{
head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = NULL;
printList();
int key;
printf("Enter the key to search\t");
scanf("%d", &key);
search(key);
return 0;
}
| $ gcc search_iterative.c $ ./a.out Linked List is 1–> 2–> 3–> 4–> NULL Enter the key to search 4 4 is present in the Linked List! $ ./a.out Linked List is 1–> 2–> 3–> 4–> NULL Enter the key to search 5 5 is not present in the Linked List! |
Recursive Solution
| 1) If head is NULL, return false. 2) If head’s data is same as key, return true; 2) Else return search(head->next, key) |
/*C code to Search an element in a Linked List*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *head = NULL;
NODE *newNode(int key)
{
NODE *temp = (NODE *)malloc(sizeof(NODE));
temp->data = key;
temp->next = NULL;
return temp;
}
bool search(NODE *head, int key)
{
if (head == NULL)
return false;
if (head->data == key)
return true;
return search(head->next, key);
}
void printList()
{
NODE *temp = head;
if (temp == NULL)
{
printf("List is empty!\n");
return;
}
printf("Linked List is\t");
while (temp != NULL)
{
printf("%d--> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main()
{
head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = NULL;
printList();
int key;
printf("Enter the key to search\t");
scanf("%d", &key);
if (search(head, key))
printf("%d is present in the Linked List!", key);
else
printf("%d is not present in the Linked List!", key);
return 0;
}
| $ gcc search_recursive.c $ ./a.out Linked List is 1–> 2–> 3–> 4–> NULL Enter the key to search 4 4 is present in the Linked List! $ ./a.out Linked List is 1–> 2–> 3–> 4–> NULL Enter the key to search 5 5 is not present in the Linked List! |
also see
| C Programming language |
Go Programming language |
| Linked List | Array |
| Stack | Queue |
| Puzzle | Reasoning |
| Aptitude | HTML |
