Problem Statement

Given a linked list and a target value, we aim to determine whether the target value exists in the linked list and, if so, at which position.

Examples

Example 1:

Input: List: 1→2→3, Element = 2
Output: True, index = 1

Different Approaches

1️⃣ Iterative Approach

Intuition:

To search for an element in a linked list, we need to traverse through all the nodes while comparing the data value of each node with the target value. If we find a node whose data matches the target value, we return true along with the position of the node. If we reach the end of the list without finding the target value, we return false.

Algorithm:

1. Start from the head of the list.
2. While traversing the list:
   1. If the data of the current node matches the target value, return true along with the position count.
   2. Move to the next node using the next pointer.
3. If we reach the end of the list without finding the target value, return false.

Code:

#include <iostream>
using namespace std;

// Define the Node structure
class Node {
public:
    int data;
    Node* next;

    // Constructor
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Function to search for an element in the linked list
pair<bool, int> searchElement(Node* head, int target) {
    int position = 1;
    Node* current = head;
    while (current != nullptr) {
        if (current->data == target) {
            return {true, position};
        }
        current = current->next;
        position++;
    }
    return {false, -1}; // Element not found
}

int main() {
    // Create a linked list
    Node* head = new Node(2);
    head->next = new Node(4);
    head->next->next = new Node(6);
    head->next->next->next = new Node(8);

    // Search for elements in the linked list
    int target1 = 6;
    int target2 = 10;
    auto result1 = searchElement(head, target1);
    auto result2 = searchElement(head, target2);

    // Print the search results
    if (result1.first) {
        cout << target1 << " found at position " << result1.second << endl;
    } else {
        cout << target1 << " not found in the linked list" << endl;
    }
    if (result2.first) {
        cout << target2 << " found at position " << result2.second << endl;
    } else {
        cout << target2 << " not found in the linked list" << endl;
    }

    return 0;
}

// Output
6 found at position 3
10 not found in the linked list

Complexity Analysis

• Time Complexity: O(n)
  • The time complexity of searching for an element in a linked list is linear with respect to the number of nodes in the list. This is because we need to traverse through all the nodes once to search for the element.
• Space Complexity: O(1)
  • The space complexity is constant because the operation requires only a constant amount of additional memory for  temporary variables, regardless of the size of the linked list.

2️⃣ Recursive Approach

Code:

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node* next;

    // Constructor to initialize the node with a value and set next to nullptr
    Node(int val) {
        this->val = val;
        next = nullptr;
    }
};

// Recursive function to search for a value in the linked list
bool search(Node* head, int target) {
    // Base case: If the current node is nullptr, the value is not found
    if (head == nullptr) {
        return false;
    }

    // If the current node's value is the target, return true
    if (head->val == target) {
        return true;
    }

    // Recursively call the function for the next node in the list
    return search(head->next, target);
}

// Function to traverse the linked list and print its values
void traverse(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list
    Node* head = new Node(1);            // First node with value 1
    head->next = new Node(2);            // Second node with value 2
    head->next->next = new Node(3);      // Third node with value 3
    head->next->next->next = new Node(4);// Fourth node with value 4
    head->next->next->next->next = new Node(5); // Fifth node with value 5

    cout << "Original List: ";
    traverse(head); // Print the original list

    int target = 3;
    if (search(head, target)) {
        cout << "Value " << target << " found in the list." << endl;
    } else {
        cout << "Value " << target << " not found in the list." << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • This is because, in the worst case, we may need to traverse all the nodes in the list, which takes linear time.
• Space Complexity: O(n)
  • In the worst case, the recursion depth will be equal to the number of nodes (n), as each recursive call processes one node.