Find and Replace feature using a Linked List

💡 Algorithm: Find and Replace using Linked List

Input:

A sentence (string), a word to find, and a replacement word.

Output:

Modified sentence after performing find and replace.

---

Steps:

1. Read the sentence from the user.

2. Split the sentence into individual words using strtok().

3. Create a linked list —
   Each node stores:

   • One word (char word[50])

   • Pointer to next node (struct Node *next)

4. Traverse the linked list:
   Compare each word in the list with the target word using strcmp().
   If a match is found, replace it with the replacement word using strcpy().

5. Print the modified list to show the new sentence.

---

Time Complexity

Operation	Complexity
Build Linked List	O(n)
Find and Replace	O(n)
Print List	O(n)
✅ Total: O(n) — very efficient for small and medium texts.

C Program Implementation

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct Node {

    char word[50];

    struct Node* next;

};

// Create a new node

struct Node* createNode(const char* word) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    strcpy(newNode->word, word);

    newNode->next = NULL;

    return newNode;

}

// Insert node at end

struct Node* insertEnd(struct Node* head, const char* word) {

    struct Node* newNode = createNode(word);

    if (head == NULL)

        return newNode;

    struct Node* temp = head;

    while (temp->next != NULL)

        temp = temp->next;

    temp->next = newNode;

    return head;

}

// Display the linked list (print sentence)

void displayList(struct Node* head) {

    struct Node* temp = head;

    while (temp != NULL) {

        printf("%s ", temp->word);

        temp = temp->next;

    }

    printf("\n");

}

// Find and replace word in the linked list

void findAndReplace(struct Node* head, const char* target, const char* replacement) {

    struct Node* temp = head;

    while (temp != NULL) {

        if (strcmp(temp->word, target) == 0) {

            strcpy(temp->word, replacement);

        }

        temp = temp->next;

    }

}

// Free the memory

void freeList(struct Node* head) {

    struct Node* temp;

    while (head != NULL) {

        temp = head;

        head = head->next;

        free(temp);

    }

}

int main() {

    char sentence[200], target[50], replacement[50];

    struct Node* head = NULL;

    char *token;

    printf("Enter a sentence:\n");

    fgets(sentence, sizeof(sentence), stdin);

    sentence[strcspn(sentence, "\n")] = '\0'; // Remove newline

    // Split sentence into words and build linked list

    token = strtok(sentence, " ");

    while (token != NULL) {

        head = insertEnd(head, token);

        token = strtok(NULL, " ");

    }

    printf("\nOriginal sentence:\n");

    displayList(head);

    printf("\nEnter the word to find: ");

    scanf("%s", target);

    printf("Enter the replacement word: ");

    scanf("%s", replacement);

    findAndReplace(head, target, replacement);

    printf("\nModified sentence:\n");

    displayList(head);

    freeList(head);

    return 0;

}

Enter a sentence:
Data structures are the backbone of efficient algorithms

Original sentence:
Data structures are the backbone of efficient algorithms

Enter the word to find: backbone
Enter the replacement word: pillar

Modified sentence:
Data structures are the pillar of efficient algorithms