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

20

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



Linked list search found

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


Linked list search not found

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; }


Topics You Might Like