Find a Node in Linked List using C++ program

In this question, we define a temp pointer and equating it with head of the Linked List. We have to keep an integer index keeping the track of the temp node. We keep on traversing while temp != NULL. On each traversal, we check whether temp's data and the user's data. If they are equal, we return the index. Else we increment index by 1 and temp to temp-> next.

At last if we don’t find the element, we return -1.

Algorithm:

• Step 1: Declare the recursive function with parameters (Node * head, int data)
• Step 2: Put Node *temp = head, int index = 0;
• Step 3: Repeat Step 4 and 5 while (temp!= NULL)
• Step 4: if(temp -> data == data) return index
• Step 5: else index++ and temp = temp->next;
• Step 6: return -1

Function:

//Function for finding the node
int findNodeInLL(Node* head, int data){
	//Used to keep track of the Node Index
	int index = 0;              
	Node * temp = head;
	//LinkedList traversal for finding the node
	while(temp!=NULL){
		if(temp->data == data){         
			//If element found return index
			return index;               
		}
		temp = temp->next;
		index++;
	}   
	//If element not found
	return -1;                  
}

C++ code

#include <bits/stdc++.h>
using namespace std;

struct Node{// linked list Node
	int data;
	Node * next;
};

Node *newNode(int k){ //defining new node
	Node *temp = (Node*)malloc(sizeof(Node)); 
	temp->data = k; 
	temp->next = NULL; 
	return temp; 
}

//Used to add new node at the end of the list
Node *addNode(Node* head, int k){
	if(head == NULL){
		head = newNode(k);
	}
	else{
		Node * temp = head;
		Node * node = newNode(k);
		while(temp->next!= NULL){
			temp = temp->next;
		}
		temp-> next = node;
	}

	return head;
}

// Used to create new linked list and return head
Node *createNewLL(){
	int cont = 1;
	int data;
	Node* head = NULL;
	while(cont){
		cout<<"Enter the data of the Node"<<endl;
		cin>>data;
		head = addNode(head,data);
		cout<<"Do you want to continue?(0/1)"<<endl;
		cin>>cont;
	}
	return head;
}

//Function for finding the node
int findNodeInLL(Node* head, int data){
	//Used to keep track of the Node Index
	int index = 0;              
	Node * temp = head;
	//LinkedList traversal for finding the node
	while(temp!=NULL){
		if(temp->data == data){         
			//If element found return index
			return index;               
		}
		temp = temp->next;
		index++;
	}   
	//If element not found
	return -1;                  
}


//Driver Main
int main(){
	Node * head = createNewLL();

	int data;
	cout<<"Enter the data of the linked list to be found."<<endl;
	cin>>data;
	int index = findNodeInLL(head,data);
	cout<<"It is present at "<<index<< endl;

	return 0;
}

Output

Enter the data of the Node
5
Do you want to continue?(0/1)
1
Enter the data of the Node
6
Do you want to continue?(0/1)
1
Enter the data of the Node
7
Do you want to continue?(0/1)
1
Enter the data of the Node
8
Do you want to continue?(0/1)
1
Enter the data of the Node
9
Do you want to continue?(0/1)
0
Enter the data of the linked list to be found.
8
It is present at 3