searching a node in singly linked list

Check whether the given key is present or not in the linked list.

Example

Linked List : 10 20 30 40 NULL.

Input

Output

Search Found

Input

100

Output

Search Not Found

Algorithm

1. Iterate the linked list using a loop.

2. If any node has the given key value, return 1.

3. If the program execution comes out of the loop (the given key is not present in the linked list), return -1.

Search Found => return 1.

Search Not Found => return -1.

Animated Tutorial

1. Iterate the linked list using a loop.

int searchNode(struct node *head, int key)
{
    struct node *temp = head;
    
    while(temp != NULL)
    {
        temp = temp->next;
    }
    
}

2. Return 1 on search found

int searchNode(struct node *head, int key)
{
    struct node *temp = head;

    while(temp != NULL)
    {
      
        if(temp->data == key)
            return 1;
      
        temp = temp->next;
    }
}

Visual Representation

Linked List : 10 20 30 NULL

Key : 20

1. temp holding the address of the head node. temp->data = 10. key = 20. temp->data != key, so move the temp variable to the next node.

2. Now, temp->data = 20. key = 20. temp->key == key. "Seach Found".

3. Return -1 on search not found

int searchNode(struct node *head, int key)
{
    struct node *temp = head;

    while(temp != NULL)
    {
        if(temp->data == key)
            return 1;
        temp = temp->next;
    }
    
    return -1;
    
}

Visual Representation

Linked List : 10 20 30 NULL

Key : 100

1. temp->data = 10. key = 100. temp->data != key. Hence move the temp variable to the next node.

2. temp->data = 20. key = 100. temp->data != key. Hence move the temp variable to the next node.

3. temp->data = 30. key = 100. temp->data != key. Hence move the temp variable to the next node which is NULL.

4. Finally, the program execution will come out of the loop. So, it will return -1.

"Search Not Found".

Implementation of searching a node in singly linked list

Example

/*
 * Program  : Searching an element in the linked list
 * Language : C
 */

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

struct node
{
    int data;
    struct node *next;
};

void addLast(struct node **head, int val)
{
    //create a new node
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = val;
    newNode->next     = NULL;

    //if head is NULL, it is an empty list
    if(*head == NULL)
         *head = newNode;
    //Otherwise, find the last node and add the newNode
    else
    {
        struct node *lastNode = *head;

        //last node's next address will be NULL.
        while(lastNode->next != NULL)
        {
            lastNode = lastNode->next;
        }

        //add the newNode at the end of the linked list
        lastNode->next = newNode;
    }

}

int searchNode(struct node *head,int key)
{
    struct node *temp = head;

    //iterate the entire linked list and print the data
    while(temp != NULL)
    {
         //key found return 1.
         if(temp->data == key)
             return 1;
         temp = temp->next;
    }
    //key not found
    return -1;
}

int main()
{
     struct node *head = NULL;

     addLast(&head,10);
     addLast(&head,20);
     addLast(&head,30);

     //change the key and try it yourself.
     if(searchNode(head,20) == 1)
         printf("Search Found\n");
     else
         printf("Search Not Found\n");

     return 0;
}