C Program to Search an Element in a Linked List

Introduction

Searching for an element in a linked list involves traversing the list from the head node to the end node and comparing each node’s data with the target value. If a match is found, the search is successful, and the position of the element (or its existence) is returned. If no match is found after traversing the entire list, the search concludes that the element is not present.

Example:

• Input: A linked list with nodes containing [10, 20, 30, 40] and the target value 30.
• Output: The program should return that the element 30 is found in the list.

Problem Statement

Create a C program that:

• Creates a singly linked list.
• Searches for a specific element in the linked list.
• Displays whether the element is found and its position in the list.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Search for an Element in the Linked List: Write a function that traverses the linked list and searches for the target element.
4. Implement the Function to Insert a Node at the End of the Linked List: Write a function to insert nodes at the end of the linked list.
5. Create a Main Function: In the main() function, create the linked list, search for an element, and display the result.

C Program to Search an Element in a Linked List

#include <stdio.h>
#include <stdlib.h>

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to search for an element in the linked list
int searchElement(struct Node* head, int target) {
    int position = 1;
    struct Node* current = head;

    while (current != NULL) {
        if (current->data == target) {
            return position;  // Element found at this position
        }
        current = current->next;
        position++;
    }

    return -1;  // Element not found in the list
}

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = new_node;
}

// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    int target, position;

    // Insert elements at the end
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);

    // Display the linked list
    printf("Linked List: ");
    displayList(head);

    // Input the element to search
    printf("Enter the element to search: ");
    scanf("%d", &target);

    // Search for the element in the linked list
    position = searchElement(head, target);

    // Display the result of the search
    if (position != -1) {
        printf("Element %d found at position %d.\n", target, position);
    } else {
        printf("Element %d not found in the linked list.\n", target);
    }

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Search for an Element in the Linked List

• The searchElement function takes a pointer to the head of the linked list (head) and the target element (target) to search for.
• It traverses the linked list, comparing each node’s data with the target value.
• If a match is found, the function returns the position of the element in the list.
• If no match is found, the function returns -1 to indicate that the element is not in the list.

Function to Insert a Node at the End of the Linked List

• The insertAtEnd function takes a double pointer to the head of the linked list (head_ref) and the data to be inserted (new_data).
• A new node is allocated dynamically using malloc().
• If the linked list is empty, the new node becomes the head of the list.
• Otherwise, the function traverses the list to the last node and updates the last node’s next pointer to point to the new node.

Function to Display the Linked List

• The displayList function traverses the linked list from the head and prints each node’s data, followed by an arrow (->), until it reaches the end (NULL).

Main Function

• The main function creates a linked list by inserting nodes at the end using the insertAtEnd function.
• It then prompts the user to enter the target element to search for.
• The searchElement function is called to search for the target element in the list, and the result is displayed.

Output Example

Example Output:

Linked List: 10 -> 20 -> 30 -> 40 -> NULL
Enter the element to search: 30
Element 30 found at position 3.

Example Output (Element Not Found):

Linked List: 10 -> 20 -> 30 -> 40 -> NULL
Enter the element to search: 50
Element 50 not found in the linked list.

Conclusion

This C program demonstrates how to search for an element in a linked list. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and linked list traversal, making it a useful example for beginners learning data structures in C programming.