Home » C++ programs

Find a Node in Linked List using C++ program

Here, we are going to write a C++ program to find a Node in the Linked List.
Submitted by Indrajeet Das, on December 21, 2018

Given a linked list and an integer N, you need to find and return index where N is present in the Linked List. Return -1 if n is not present in the Linked List.

Indexing of nodes starts from 0.

    Input format:

    Line 1: Linked list elements (separated by space and terminated by -1)
    Line 2: Integer n 

    Output format:
    Index

Example:

    Sample Input 1:
    3 4 5 2 6 1 9 -1
    5

    Sample Output 1:
    2

    Sample Input 2:
    3 4 5 2 6 1 9 -1
    6

    Sample Output 2:
    4

Description:

In this question, we are given a linked list and a data. We have to find the index of the Node which contains the data.

Example:

    2->1->5->4->3->NULL
    In this list 5 is at 2nd index.

Solution explanation:

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