Q:

Find a Node in Linked List using C++ program

belongs to collection: C++ programs on various topics

mahmoud2506
Save to bookmark
|
2022-05-05
|
  271 
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

 

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

All Answers

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

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

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

total answers (1)

C++ programs on various topics
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Merge sort for single linked lists... >>
<< Eliminate duplicates from Linked List using C++ pr...