Thursday, 06 July 2017 03:10

Search an element in a Linked List (Iterative and Recursive)

Written by
Rate this item

Write a C function that searches a given key ‘x’ in a given singly linked list. The function should return true if x is present in linked list and false otherwise.

For example, if the key to be searched is 15 and linked list is 14->21->11->30->10, then function should return false. If key to be searched is 14, then the function should return true.

Iterative Solution

2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
a) current->key is equal to the key being searched return true.
b) current = current->next
4) Return false

Following is iterative C implementation of above algorithm to search a given key.

// Iterative C program to search an element in linked list
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h

struct Node
{
int key;
struct Node* next;
};

/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_key)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the key  */
new_node->key  = new_key;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Checks whether the value x is present in linked list */
bool search(struct Node* head, int x)
{
struct Node* current = head;  // Initialize current
while (current != NULL)
{
if (current->key == x)
return true;
current = current->next;
}
return false;
}

/* Driver program to test count function*/
int main()
{
int x = 21;

/* Use push() to construct below list
14->21->11->30->10  */

return 0;
}
Output:
Yes

Recursive Solution

1) If head is NULL, return false.
2) If head's key is same as x, return true;

Following is recursive C implementation of above algorithm to search a given key.

// Recursive C program to search an element in linked list
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct Node
{
int key;
struct Node* next;
};

/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_key)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the key  */
new_node->key  = new_key;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Checks whether the value x is present in linked list */
bool search(struct Node* head, int x)
{
// Base case
return false;

// If key is present in current node, return true
return true;

// Recur for remaining list
}

/* Driver program to test count function*/
int main()
{
int x = 21;

/* Use push() to construct below list
14->21->11->30->10  */

return 0;

}
Output:
Yes 