Search an element in a Linked List (Iterative and Recursive) | DSA in C++ - Software Development PDF Download

Introduction

In this article, we will explore how to search for an element in a linked list using both iterative and recursive approaches in C++. We will provide simple code examples, along with explanations, to help beginners understand the concept easily.

Linked List Overview

A linked list is a data structure that consists of a sequence of nodes, where each node contains a data element and a reference (or a pointer) to the next node. The last node in the list points to NULL, indicating the end of the list.

Searching in a Linked List

Searching for an element in a linked list involves traversing through the list and comparing each node's data with the target element until a match is found or the end of the list is reached.

Iterative Approach

In the iterative approach, we use a loop to traverse the linked list until we find the desired element or reach the end of the list. The steps involved are as follows:

• Start from the head node.
• Iterate through the list, comparing the data of each node with the target element.
• If a match is found, return true.
• If the end of the list is reached without a match, return false.

Recursive Approach

In the recursive approach, we use a recursive function to search for the element in the linked list. The steps involved are as follows:

• Base case: If the current node is NULL (end of the list), return false.
• If the current node's data matches the target element, return true.
• Otherwise, recursively call the search function on the next node.

Code Examples

Now let's look at the implementation of both the iterative and recursive approaches.

#include <iostream>

// Node structure for a linked list

struct Node {

    int data;

    Node* next;

};

// Iterative search function

bool iterativeSearch(Node* head, int target) {

    Node* current = head;

    while (current != NULL) {

        if (current->data == target) {

            return true;  // Element found

        }

        current = current->next;

    }

    return false;  // Element not found

}

// Recursive search function

bool recursiveSearch(Node* current, int target) {

    if (current == NULL) {

        return false;  // Element not found

    }

    if (current->data == target) {

        return true;  // Element found

    }

    return recursiveSearch(current->next, target);

}

// Driver code to test the search functions

int main() {

    // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5

    Node* head = new Node();

    Node* second = new Node();

    Node* third = new Node();

    Node* fourth = new Node();

    Node* fifth = new Node();   

    head->data = 1;

    head->next = second;

    second->data = 2;

    second->next = third;

    third->data = 3;

    third->next = fourth;

    fourth->data = 4;

    fourth->next = fifth;

    fifth->data = 5;

    fifth->next = NULL;    

    // Test the iterative search function

    int target = 3;

    bool foundIterative = iterativeSearch(head, target);

    std::cout << "Iterative search: ";

   if (foundIterative) {

        std::cout << "Element " << target << " found in the linked list." << std::endl;

    } else {

        std::cout << "Element " << target << " not found in the linked list." << std::endl;

    }

    // Test the recursive search function

    bool foundRecursive = recursiveSearch(head, target);

    std::cout << "Recursive search: ";

    if (foundRecursive) {

        std::cout << "Element " << target << " found in the linked list." << std::endl;

    } else {

        std::cout << "Element " << target << " not found in the linked list." << std::endl;

    }

    return 0;

}

Output:

Iterative search: Element 3 found in the linked list.

Recursive search: Element 3 found in the linked list.

Sample Problems and Solutions

Here are a few sample problems related to searching in a linked list:

Problem 1: Write a function to count the occurrences of a given element in a linked list.

int countOccurrences(Node* head, int target) {

    int count = 0;

    Node* current = head;

    while (current != NULL) {

        if (current->data == target) {

            count++;

        }

        current = current->next;

    }

    return count;

}

Problem 2: Given two linked lists, determine if they intersect and return the intersecting node.

Node* findIntersection(Node* head1, Node* head2) {

    Node* current1 = head1;

    Node* current2 = head2;

    while (current1 != current2) {

        current1 = (current1 == NULL) ? head2 : current1->next;

        current2 = (current2 == NULL) ? head1 : current2->next;

    }

    return current1;

}

Conclusion

In this article, we discussed how to search for an element in a linked list using both iterative and recursive approaches in C++. We provided code examples and explanations for each approach. Additionally, we explored a couple of sample problems related to searching in a linked list. By understanding these concepts, beginners can gain a solid foundation in linked list operations and algorithms.