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.