C Program to perform Searching in a linked list

Searching in a linked list is the process of finding a specific element stored in the list. Since the nodes are not stored in continuous memory, we must check each node one by one. The search starts from the head node and continues until the required value is found or the list ends. This operation is widely used in data structures to locate data efficiently.

What is a Linked List?

A linked list is a fundamental data structure in C programming that consists of a sequence of connected nodes. Each node contains two main parts:

• Data – to store the value
• Pointer – to store the address of the next node

Unlike arrays, linked lists use dynamic memory allocation, which means the size of the list can grow or shrink during program execution without any fixed limit. This makes linked lists very flexible in nature. They are highly efficient for insertion and deletion operations because no shifting of elements is required. However, accessing elements is slower compared to arrays because the list must be traversed sequentially.

What is Searching Operation in a linked list?

The searching operation in a linked list is the process of finding a specific element by traversing the list from the head node to the last node and comparing each node’s data with the required value. Since a linked list does not support direct access like an array, every node must be checked one by one until the element is found or the list ends. This operation helps in locating data stored at an unknown position in the list.

Example:

If the linked list is 10 → 20 → 30 → 40, and we want to search for 30, the search will start from 10, then check 20, and finally find 30 at the third position.

Linked List Search Algorithm

1. Start from the head node
2. Check if list is empty → if yes, display message and exit
3. Read the target value to search
4. Traverse through each node sequentially
5. Compare current node’s data with target value
6. If match found → display location and exit
7. If end reached without match → display “not found” message
8. End

C Code to Search an Element in a Linked List

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

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;

struct node* createNode() {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->next = NULL;
    return newNode;
}

void insertNode() {
    struct node *temp, *ptr;
    temp = createNode();
    
    printf("Enter element to insert: ");
    scanf("%d", &temp->data);
    
    if (head == NULL) {
        head = temp;
    } else {
        ptr = head;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
    printf("Element inserted successfully!\n");
}

void searchElement() {
    struct node *temp;
    int target, position = 1, found = 0;
    
    temp = head;
    if (temp == NULL) {
        printf("Linked List is empty\n");
        return;
    }
    
    printf("Enter element to search: ");
    scanf("%d", &target);
    
    while (temp != NULL) {
        if (temp->data == target) {
            printf("Element found at position %d\n", position);
            found = 1;
            break;
        }
        position++;
        temp = temp->next;
    }
    
    if (!found) {
        printf("Element not found in linked list\n");
    }
}

void viewList() {
    struct node *temp = head;
    if (temp == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int menu() {
    int choice;
    printf("\n1. Insert element");
    printf("\n2. Search element");
    printf("\n3. View linked list");
    printf("\n4. Exit");
    printf("\nEnter choice: ");
    scanf("%d", &choice);
    return choice;
}

int main() {
    printf("** Linked List Search Program **\n");
    while (1) {
        switch (menu()) {
            case 1: insertNode(); break;
            case 2: searchElement(); break;
            case 3: viewList(); break;
            case 4: exit(0);
            default: printf("Invalid choice\n");
        }
    }
    return 0;
}

Output

** Linked List Search Program **

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 1
Enter element to insert: 10
Element inserted successfully!

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 1
Enter element to insert: 20
Element inserted successfully!

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 1
Enter element to insert: 30
Element inserted successfully!

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 3
Linked List: 10 → 20 → 30 → NULL

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 2
Enter element to search: 20
Element found at position 2

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 2
Enter element to search: 40
Element not found in linked list

1. Insert element
2. Search element
3. View linked list
4. Exit
Enter choice: 4
[Program terminates]

Code Explanation

1. Node Structure Definition

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;

Defines the basic building block of a linked list:

• data: Stores integer value
• next: Pointer to the subsequent node
• head: Global pointer initialized to NULL, representing empty list

2. Node Creation Function

struct node* createNode() {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->next = NULL;
    return newNode;
}

Creates and initializes a new node:

• Allocates memory using malloc()
• Checks for allocation failure
• Initializes next pointer to NULL
• Returns pointer to newly created node

3. Insertion Function

void insertNode() {
    struct node *temp, *ptr;
    temp = createNode();
    
    printf("Enter element to insert: ");
    scanf("%d", &temp->data);
    
    if (head == NULL) {
        head = temp;
    } else {
        ptr = head;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
    printf("Element inserted successfully!\n");
}

Inserts new node at the end of the list:

• If list empty: new node becomes head
• If list not empty: traverse to last node and append new node

4. Search Function

void searchElement() {
    struct node *temp;
    int target, position = 1, found = 0;
    
    temp = head;
    if (temp == NULL) {
        printf("Linked List is empty\n");
        return;
    }
    
    printf("Enter element to search: ");
    scanf("%d", &target);
    
    while (temp != NULL) {
        if (temp->data == target) {
            printf("Element found at position %d\n", position);
            found = 1;
            break;
        }
        position++;
        temp = temp->next;
    }
    
    if (!found) {
        printf("Element not found in linked list\n");
    }
}

Implements linear search algorithm:

• Checks for empty list
• Accepts search target from user
• Traverses list comparing each node’s data
• If found: displays position and exits
• If not found: displays appropriate message

5. Traversal Function

void viewList() {
    struct node *temp = head;
    if (temp == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Displays all elements in the list:

• Uses arrow notation (→) to visualize connections
• Terminates display with NULL marker

6. Menu Function

int menu() {
    int choice;
    printf("\n1. Insert element");
    printf("\n2. Search element");
    printf("\n3. View linked list");
    printf("\n4. Exit");
    printf("\nEnter choice: ");
    scanf("%d", &choice);
    return choice;
}

Provides user interface with four options for list operations.

7. Main Function

int main() {
    printf("** Linked List Search Program **\n");
    while (1) {
        switch (menu()) {
            case 1: insertNode(); break;
            case 2: searchElement(); break;
            case 3: viewList(); break;
            case 4: exit(0);
            default: printf("Invalid choice\n");
        }
    }
    return 0;
}

Implements interactive program loop that processes user choices until exit.

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	Element is found at the head.
Average Case	O(n)	Element is somewhere in the middle.
Worst Case	O(n)	Element is at the end or not present.

Space Complexity

Operation	Space Complexity	Explanation
Search Element	O(1)	Only one pointer is used for traversal; no extra space needed.

Linked List Search Example

List: 10 → 20 → 30 → 40 → NULL
Searching for 30:
Step 1: Compare 10 with 30 → No match
Step 2: Compare 20 with 30 → No match  
Step 3: Compare 30 with 30 → Match found at position 3
Total comparisons: 3

List: 10 → 20 → 30 → 40 → NULL
Searching for 50:
Step 1: Compare 10 with 50 → No match
Step 2: Compare 20 with 50 → No match  
Step 3: Compare 30 with 50 → No match
Step 4: Compare 40 with 50 → No match
Step 5: Reach NULL → Element not found
Total comparisons: 4

Search Algorithm Variations

There are two variations of search algorithm on linked list:

1. Search with position return
2. Search with node pointer return

1. Search with position return

// Alternative: Search with position return
int searchWithPosition(int target) {
    struct node *temp = head;
    int position = 1;
    
    while (temp != NULL) {
        if (temp->data == target) {
            return position;
        }
        position++;
        temp = temp->next;
    }
    return -1;  // Element not found
}

2. Search with node pointer return

// Alternative: Search with node pointer return
struct node* searchWithPointer(int target) {
    struct node *temp = head;
    
    while (temp != NULL) {
        if (temp->data == target) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;  // Element not found
}

Important Considerations

• Linear Search Only: Linked lists don’t support binary search due to lack of random access
• No Early Optimization: Unlike sorted arrays, linked lists can’t optimize search based on value comparisons
• Memory Efficiency: Search operations use only O(1) extra space for temporary pointers
• Performance Impact: Frequent searches on large linked lists may benefit from alternative data structures

Conclusion

Searching in linked lists is a fundamental linear operation with O(n) time complexity. While not as efficient as array indexing for random access, linked lists excel in dynamic memory management scenarios where frequent insertions and deletions are required. The search implementation demonstrates core linked list traversal principles and serves as a building block for more complex operations like deletion at specific positions or value-based modifications.

Key Insight: Choose linked lists when your application prioritizes dynamic size changes over fast search operations. For search-intensive applications, consider balanced binary search trees or hash tables as alternatives.