Q:

Find a Node in Linked List using C++ program

mahmoud2506
Save to bookmark
|
2022-05-08
|
  210 
0

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.

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-08
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Data Structure programs using C and C++ (Linked List Programs)
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C program to convert a Binary Tree into a Singly L... >>
<< Eliminate duplicates from Linked List using C++ pr...