Search an element in a Linked List (Iterative and Recursive)
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.
