Searching in a Linked List | Linked List Operations

10 min read

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 pointer
struct 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 list
scanf("%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 empty
if(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

searching in a linked list

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 pointer
struct 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 empty
if(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 case
if (head == NULL)
return 0;

// If key is present in current node, return true
if (head->data == search_data)
{
return 1;
}

// Recur for remaining list
head = head -> next;
return search_element(search_data);
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
// Print the list
while(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 list
scanf("%d",&element);
int status = search_element(element);
if(status == 1)
{
printf("Element is found in the linked list\n");
}
else
printf("\nElement is not found in the linked list\n");

return 0;
}




OUTPUT

searching in linked list recursively

Time Complexity : O(n)

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

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error