search an element in a linked list

C Program to Search an element in a Linked List using Iterative and Recursive

In this article, we will learn how to search an element in a linked-list. It is a very simple program that is generally asked in the interview.

For example:

Linked List: 13-->19-->20-->22-->11-->NULL
Enter Element: 20

Result: 
Element Found

Linked List: 14-->22-->10-->2-->7-->NULL
Enter Element: 3

Result: 
Element Not Found


 

Here we will see two methods to find the element, iteration, and recursion.

Iteration method

Steps to find the element in a given linked list

  • Assign the address of the first node to a temporary node pointer (Tmp).
  • Traverse the linked list until node pointer (Tmp != NULL).
  • Check the element in every iteration of the linked-list, if the given element is matched with tmp->iData then return TRUE else return FALSE.

Source Code

int SearchTheElement(NodePointer pNode,int iElement)
{
    //Clear the screen
    printf("\nDisplay Linked List: \n\n");
    while (pNode != NULL)
    {
        if(pNode->iData == iElement)
        {
            return TRUE;
        }
        else
        {
            pNode = pNode->pNextNode;
        }

    }
    return FALSE;

}

 

Example code to search an element in a given linked list using iterative

In a given example code, first, we will create a linked list as per the choice. when the linked list has created then we will search the element in a created linked list using the iterative method.

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

#define TRUE   1
#define FALSE  0


// Creating Node
struct Node
{
    int iData;
    struct Node *pNextNode;
};


// Define the new type Node type and Node pointer
typedef struct Node NodeType, * NodePointer;


/* Paas the reference of the head pointer of a list and
  an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData)
{
    int iRetValue = -1;

    NodePointer pLastNode = NULL;
    NodePointer pNewNode = NULL;

    //Give the Address of first Node
    pLastNode = *pHead;

    // Call malloc to allocate memory in heap for the new node
    pNewNode = malloc(sizeof(NodeType));

    if( pNewNode != NULL) //Check allocated memory
    {
        pNewNode->iData = iUserData; //put the desire Data

        pNewNode->pNextNode = NULL; //Give the Address of first Node

        iRetValue = 0; // Update the return value

    }
    // If there is no node in beginning
    if(pLastNode == NULL)
    {
        *pHead = pNewNode;
    }
    else
    {
        // Find the address of last node
        while( pLastNode ->pNextNode != NULL)
        {
            pLastNode = pLastNode ->pNextNode;
        }

        // Assign last node address
        pLastNode ->pNextNode = pNewNode;

    }

    return iRetValue;
}


/* Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer *pHead)
{
    NodePointer pTmpNode = NULL;
    NodePointer pFirstNode = NULL;
    //Assign the Address of first node
    pFirstNode = *pHead;

    /*check if pFirstNode is NULL, then now list is empty,
    so assign NULL to head and return.*/
    while (pFirstNode != NULL)
    {
        /*Save the pFirstNode in a pTmpNode node pointer*/

        pTmpNode = pFirstNode ;

        /*Assign the address of next on your list*/
        pFirstNode = pFirstNode->pNextNode;

        //Free the allocated memory
        free(pTmpNode );
    }
    //Assign NULL to the head pointer
    *pHead = NULL;

}



// This function use to prints the data of the list from the beginning
//to the given list.

void PrintTheList(NodePointer pNode)
{
    //Clear the screen

    printf("\nDisplay Linked List: \n\n");
    while (pNode != NULL)
    {
        printf("\n %d\n",pNode->iData);
        pNode = pNode->pNextNode;
    }

    printf("\n\n");

}



//Create a number of nodes
int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
    int iData = 0;
    int iRetValue = -1;
    int iCount = 0;
    NodePointer pNewNode = NULL;

    for(iCount =0; iCount < iNumberofNode; iCount++)
    {
        /*Enter desire data*/
        printf("\n\nEnter the Data = ");
        scanf("%d",&iData);

        if((*pHead) == NULL)
        {
            // Call malloc to allocate memory in heap for the first node
            pNewNode = malloc(sizeof(NodeType));
            if( pNewNode != NULL) //Check allocated memory
            {
                pNewNode->iData = iData; //put the desire Data

                pNewNode->pNextNode = NULL; //Give the Address of first Node

                *pHead = pNewNode; /*Assign the address of
                       first node to the head pointer*/

                iRetValue = 0; // Update the return value

            }
        }
        else
        {
            //Add the Node at the End
            iRetValue = InsertNodeAtEnd(pHead,iData);

        }
    }

    return iRetValue;
}


/*
This function use to search the given element
in a given linked list using the itterative method
*/
int SearchTheElement(NodePointer pNode,int iElement)
{
    //Clear the screen
    printf("\nDisplay Linked List: \n\n");
    while (pNode != NULL)
    {
        if(pNode->iData == iElement)
        {
            return TRUE;
        }
        else
        {
            pNode = pNode->pNextNode;
        }
    }
    return FALSE;

}


//Driver main program
int main(int argc, char *argv[])
{
    int iNumberNode =0;
    int LengthOfList = 0;
    int iData = 0;
    int iFlag = -1;


    /*Start with the empty list */
    NodePointer head = NULL;


    printf("\n\nEnter the number of nodes = ");
    scanf("%d",&iNumberNode);

    //Create a linked list of three node
    CreateLinkedList(&head,iNumberNode);

    printf("\n\nCreated linked list\n\n");
    PrintTheList(head);

    printf("\n\n\nEnter the element which you want to find:");

    scanf("%d",&iData);

    //Print the created list and get the length
    iFlag = SearchTheElement(head,iData);

    if(iFlag == TRUE)
    {
        printf("Element Found\n");
    }
    else
    {
        printf("Element Not Found\n");
    }

    //Free the allocated memory
    FreeAllocatedMemory(&head);

    return 0;
}

OutPut 1:

C Program to find an element in a Linked List using Iterative and Recursive

 

 

 

 

 

 

 

 

 

OutPut 2:

C Program to Search an element in a Linked List using Iterative and Recursive

 

 

 

 

 

 

 

 

 

If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.

Your free trial is waiting

 

Recursion Method:

Steps to search the element using the recursive method
  • If head pointer (pNode->iData ) is NULL, return FALSE.
  • If current node element (pNode->iData ) is same as iElement, return TRUE.
  • Else call return SearchTheElement ( pNode->pNextNode,iElement ).

Source Code

int SearchTheElement(NodePointer pNode,int iElement)
{

    if(pNode == NULL)
    {
        return FALSE;
    }
    else
    {
        if(pNode->iData == iElement)
        {
            return TRUE;
        }
        else
        {
            return SearchTheElement(pNode->pNextNode,iElement);
        }
    }

}

 

Example code to find an element in a given linked list using recursion

In a given example code, first, we will create a linked list as per the choice. when the linked list has created then we will search the element in a created linked list using the recursive method.

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

#define TRUE   1
#define FALSE  0


// Creating Node
struct Node
{
    int iData;
    struct Node *pNextNode;
};


// Define the new type Node type and Node pointer
typedef struct Node NodeType, * NodePointer;



/* Paas the reference of the head pointer of a list and
  an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData)
{
    int iRetValue = -1;

    NodePointer pLastNode = NULL;
    NodePointer pNewNode = NULL;

    //Give the Address of first Node
    pLastNode = *pHead;

    // Call malloc to allocate memory in heap for the new node
    pNewNode = malloc(sizeof(NodeType));

    if( pNewNode != NULL) //Check allocated memory
    {
        pNewNode->iData = iUserData; //put the desire Data

        pNewNode->pNextNode = NULL; //Give the Address of first Node

        iRetValue = 0; // Update the return value

    }
    // If there is no node in beginning
    if(pLastNode == NULL)
    {
        *pHead = pNewNode;
    }
    else
    {
        // Find the address of last node
        while( pLastNode ->pNextNode != NULL)
        {
            pLastNode = pLastNode ->pNextNode;
        }

        // Assign last node address
        pLastNode ->pNextNode = pNewNode;

    }

    return iRetValue;
}

/*Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer *pHead)
{
    NodePointer pTmpNode = NULL;
    NodePointer pFirstNode = NULL;
    //Assign the Address of first node
    pFirstNode = *pHead;

    /*check if pFirstNode is NULL, then now list is empty,
    so assign NULL to head and return.*/
    while (pFirstNode != NULL)
    {
        /*Save the pFirstNode in a pTmpNode node pointer*/

        pTmpNode = pFirstNode ;

        /*Assign the address of next on your list*/
        pFirstNode = pFirstNode->pNextNode;

        //Free the allocated memory
        free(pTmpNode );
    }
    //Assign NULL to the head pointer
    *pHead = NULL;

}



// This function use to prints the data of the list from the beginning
//to the given list.

void PrintTheList(NodePointer pNode)
{
    //Clear the screen

    printf("\nDisplay Linked List: \n\n");
    while (pNode != NULL)
    {
        printf("\n %d\n",pNode->iData);
        pNode = pNode->pNextNode;
    }

    printf("\n\n");

}



//Create a number of nodes
int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
    int iData = 0;
    int iRetValue = -1;
    int iCount = 0;
    NodePointer pNewNode = NULL;

    for(iCount =0; iCount < iNumberofNode; iCount++)
    {
        /*Enter desire data*/
        printf("\n\nEnter the Data = ");
        scanf("%d",&iData);

        if((*pHead) == NULL)
        {
            // Call malloc to allocate memory in heap for the first node
            pNewNode = malloc(sizeof(NodeType));
            if( pNewNode != NULL) //Check allocated memory
            {
                pNewNode->iData = iData; //put the desire Data

                pNewNode->pNextNode = NULL; //Give the Address of first Node

                *pHead = pNewNode; /*Assign the address of
  first node to the head pointer*/

                iRetValue = 0; // Update the return value

            }
        }
        else
        {
            //Add the Node at the End
            iRetValue = InsertNodeAtEnd(pHead,iData);

        }
    }

    return iRetValue;
}


/*
This function use to search the given element
in a given linked list using the recursive method
*/
int SearchTheElement(NodePointer pNode,int iElement)
{

    if(pNode == NULL)
    {
        return FALSE;
    }
    else
    {
        if(pNode->iData == iElement)
        {
            return TRUE;
        }
        else
        {
            return SearchTheElement(pNode->pNextNode,iElement);
        }
    }

}


//Driver main program
int main(int argc, char *argv[])
{
    int iNumberNode =0;
    int LengthOfList = 0;
    int iData = 0;
    int iFlag = -1;


    /*Start with the empty list */
    NodePointer head = NULL;


    printf("\n\nEnter the number of nodes = ");
    scanf("%d",&iNumberNode);

    //Create a linked list of three node
    CreateLinkedList(&head,iNumberNode);

    printf("\n\nCreated linked list\n\n");
    PrintTheList(head);

    printf("\n\n\nEnter the element which you want to find:");

    scanf("%d",&iData);

    //Print the created list and get the length
    iFlag = SearchTheElement(head,iData);

    if(iFlag == TRUE)
    {
        printf("Element Found\n");
    }
    else
    {
        printf("Element Not Found\n");
    }

    //Free the allocated memory
    FreeAllocatedMemory(&head);

    return 0;
}

 

OutPut 1:

 

 

 

 

 

 

 

 

 

OutPut 2:

 

 

 

 

 

 

 

 

 

 

Recommended Post