Search element in linked list using C++

To search for an element in a linked list, we must iterate through the entire linked list, compare each node with the required data, and continue searching until we get a match. Because linked lists do not provide random access, we must start searching from the first node.

We get an integer linked list and an integer key. We need to find if this key exists in our linked list. We can do a simple linear search in the linked list to find the key. If it exists, we can return "Yes"; otherwise, "No"

Let’s look at some input and output scenarios -

We have fetched a list in which we need to find if the element is present in the list and get the corresponding output using the provided key of 3 -

Input Data: [ 10, 4, 5, 4, 10, 1, 3, 5]
Output: Yes

Let's consider another scenario with key 5 -

Input Data: [ 1, 4, 9, 4, 10, 1, 3, 6]
Output: No

Algorithm (steps)

The following are the algorithms/steps that need to be followed to perform the required task -

• Set the header to empty.

• Add some items to the linked list

• Get the items to be searched entered by the user.

• Linearly traverse the linked list from beginning to end until reaching an empty node.

• Check each node to see if the data value matches the item being searched for.

• Returns the index of the node where the data is found. If not found, go to the next node.

Example

For example, we have a linked list, such as "52->4651->42->5->12587->874->8->null", whose key is 12587. The C program that implements this example is given below -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   while(head) {
      if(head->val == key) {
         cout << "Yes";
         return;
      }
      head = head->next;
   }
   cout << "No";
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

Output

Yes

Example

Now we will use recursive method to solve the same problem -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   if(head == NULL) {
      cout << "No";
   } else if(head->val == key) {
      cout << "Yes";
   } else {
      solve(head->next, key);
   }
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

Output

Yes

in conclusion

The time complexity is O(n). We use an iterative approach to solve this problem. Try this problem recursively.

The above is the detailed content of Search element in linked list using C++. For more information, please follow other related articles on the PHP Chinese website!