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:
OutPut 2:
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
- Introduction to Linked List.
- Linked List Insertion.
- Delete a Linked List node.
- Generic Linked List in C
- Write a function to reverse a linked list
- Bubble sort in C with characteristics.
- File handling in C.