Part 3 - Searching

Searching in Linked List

1. Searching in a Custom Singly Linked List

#include <bits/stdc++.h>
using namespace std;

// Linked list node
class Node 
{ 
public:
    int key; 
    Node* next; 
}; 

// Add a new node at the front
void push(Node** head_ref, int new_key) 
{ 
    Node* new_node = new Node();
    new_node->key = new_key; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

// Search for a value in the linked list
bool search(Node* head, int x) 
{ 
    Node* current = head; 
    while (current != NULL) 
    { 
        if (current->key == x) 
            return true; 
        current = current->next; 
    } 
    return false; 
} 

int main() 
{ 
    Node* head = NULL; 
    int x = 21; 

    // Construct list: 14->21->11->30->10
    push(&head, 10); 
    push(&head, 30); 
    push(&head, 11); 
    push(&head, 21); 
    push(&head, 14); 

    search(head, 21) ? cout << "Yes" : cout << "No"; 
    return 0; 
}

Explanation:

• Node class represents each node in the linked list.
• push adds a new node at the beginning.
• search traverses the list iteratively to find the key.

2. Searching in STL std::list

C++ Standard Template Library (STL) provides the list container which can be used to implement a linked list. Searching can be done using the std::find algorithm.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main() {
    list<int> l = {14, 21, 11, 30, 10};
    int x = 21;

    auto it = find(l.begin(), l.end(), x);

    if (it != l.end())
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

Explanation:

• std::list is a doubly linked list implementation.
• std::find iterates through the list to locate the element.
• Returns an iterator to the element if found, or l.end() if not found.