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. By Indrajeet Das Last updated : August 01, 2023

Problem Statement

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

Problem 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.

2->1->5->4->3->NULL
In this list 5 is at 2^nd 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 / Pseudo Code

//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++ Program to Find a Node in Linked List

#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;
}

// Main code
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