Why Strings Are a Data Structure Not Just Text in DSA C - Why This Pattern

Mental Model

A string is more than just letters; it is a sequence of characters stored in order, like a chain of boxes each holding one letter.

Analogy: Imagine a necklace made of beads where each bead is a letter. The order and connection of beads matter, not just the letters themselves.

S -> t -> r -> i -> n -> g -> null
↑
head

Dry Run Walkthrough

Input: string: "cat" stored as characters in sequence

Goal: Show how a string is stored as a sequence of characters linked in order, not just a word

Step 1: Store 'c' as first character in sequence

c -> null
↑ head

Why: We start the string with the first character stored at the beginning

Step 2: Add 'a' after 'c' in sequence

c -> a -> null
↑ head

Why: Each character is stored next to the previous one to keep order

Step 3: Add 't' after 'a' in sequence

c -> a -> t -> null
↑ head

Why: The string ends with the last character pointing to null to mark the end

Result:

c -> a -> t -> null
String stored as sequence of characters, not just text

Annotated Code

DSA C

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

// Node structure for each character in string
typedef struct CharNode {
    char ch;
    struct CharNode* next;
} CharNode;

// Function to create a new node
CharNode* createNode(char c) {
    CharNode* newNode = (CharNode*)malloc(sizeof(CharNode));
    newNode->ch = c;
    newNode->next = NULL;
    return newNode;
}

// Function to build linked list string from char array
CharNode* buildString(const char* str) {
    if (str[0] == '\0') return NULL; // empty string
    CharNode* head = createNode(str[0]); // create first node
    CharNode* curr = head;
    for (int i = 1; str[i] != '\0'; i++) {
        curr->next = createNode(str[i]); // link next character
        curr = curr->next; // move to next node
    }
    return head;
}

// Function to print the linked list string
void printString(CharNode* head) {
    CharNode* curr = head;
    while (curr != NULL) {
        printf("%c -> ", curr->ch); // print character
        curr = curr->next; // move forward
    }
    printf("null\n");
}

int main() {
    const char* input = "cat";
    CharNode* stringList = buildString(input);
    printString(stringList);
    return 0;
}

CharNode* head = createNode(str[0]); // create first node

start string with first character node

curr->next = createNode(str[i]); // link next character

add next character node linked to previous

curr = curr->next; // move to next node

advance current pointer to newly added node

while (curr != NULL) { printf("%c -> ", curr->ch); curr = curr->next; }

traverse and print each character node in order

Output

c -> a -> t -> null

Complexity Analysis

Time: O(n) because we create and print each character node once for n characters

Space: O(n) because we store each character in its own node in memory

vs Alternative: Compared to storing as plain text, linked nodes allow easy insertion or deletion without shifting all characters

Edge Cases

empty string ""

returns NULL pointer, no nodes created

DSA C

if (str[0] == '\0') return NULL; // empty string

single character string "a"

creates one node with 'a' and next as NULL

DSA C

CharNode* head = createNode(str[0]); // create first node

When to Use This Pattern

When you see problems about storing or manipulating text character by character, think of strings as linked sequences to handle changes efficiently.

Common Mistakes

Mistake: Treating strings as just text without structure, ignoring how characters are stored and linked
Fix: Understand strings as sequences of connected characters, each stored in nodes or array positions

Summary

Strings store characters in order as a sequence, not just as text.

Use this when you need to manipulate characters individually or efficiently.

The key is to see strings as connected characters, like beads on a string, not just words.

Practice

1. Why are strings considered a data structure and not just plain text?

easy

A. Because strings store characters in a sequence that can be accessed and manipulated.

B. Because strings only contain letters and no other data.

C. Because strings are always immutable and cannot be changed.

D. Because strings are only used for displaying text on screen.

Solution

1. Step 1: Understand what a data structure is

   A data structure organizes data so it can be accessed and changed efficiently.

2. Step 2: Analyze string properties

   Strings store characters in order and allow access to each character by position, making them a data structure.

3. Final Answer:

   Because strings store characters in a sequence that can be accessed and manipulated. -> Option A

4. Quick Check:

   Strings = sequence + access [OK]

Hint: Strings hold ordered characters, not just text [OK]

Common Mistakes:

• Thinking strings only hold letters
• Believing strings cannot be changed
• Assuming strings are only for display

2. Which of the following is the correct way to declare a string in C?

easy

A. char str = 'hello';

B. char str[] = "hello";

C. string str = "hello";

D. char str = "hello";

Solution

1. Step 1: Recall C string declaration syntax

   In C, strings are arrays of characters ending with a null character '\0'.

2. Step 2: Check each option

   char str[] = "hello"; declares a char array initialized with a string literal correctly.

3. Final Answer:

   char str[] = "hello"; -> Option B

4. Quick Check:

   C strings = char array + null terminator [OK]

Hint: Use char array with double quotes for strings in C [OK]

Common Mistakes:

• Using single quotes for strings
• Using 'string' type which doesn't exist in C
• Declaring char variable for whole string

3. What will be the output of this C code?

char str[] = "abc";
printf("%c", str[1]);

medium

A. b

B. a

C. c

D. Compilation error

Solution

1. Step 1: Understand string indexing in C

   Strings are arrays; indexing starts at 0, so str[0] = 'a', str[1] = 'b'.

2. Step 2: Identify printed character

   printf prints str[1], which is 'b'.

3. Final Answer:

   b -> Option A

4. Quick Check:

   Index 1 of "abc" = 'b' [OK]

Hint: Remember C arrays start at index 0 [OK]

Common Mistakes:

• Confusing index 1 with index 0
• Expecting whole string output
• Thinking code causes error

4. Find the error in this C code snippet that tries to print the length of a string:

char str[] = "hello";
int len = sizeof(str);
printf("%d", len);

medium

A. printf format specifier %d is wrong for int

B. str is not initialized properly

C. sizeof returns size in bytes including null, not string length

D. No error, code works correctly

Solution

1. Step 1: Understand sizeof on arrays

   sizeof(str) returns total bytes including the null character, not the string length.

2. Step 2: Difference between sizeof and strlen

   strlen(str) returns length excluding null; sizeof includes it, so result differs.

3. Final Answer:

   sizeof returns size in bytes including null, not string length -> Option C

4. Quick Check:

   sizeof != string length [OK]

Hint: Use strlen() for string length, not sizeof() [OK]

Common Mistakes:

• Using sizeof to get string length
• Ignoring null terminator in size
• Assuming code prints length correctly

5. Given the string char str[] = "data";, which code snippet correctly reverses the string in place?

hard

A. str = "atad";

B. for(int i = 0; i < 4; i++) { str[i] = str[3 - i]; }

C. int i = 0; while(str[i] != '\0') { str[i] = str[i+1]; i++; }

D. int i = 0, j = 3; while(i < j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; }

Solution

1. Step 1: Understand in-place reversal logic

   Swapping characters from start and end moving towards center reverses the string.

2. Step 2: Analyze each option

   int i = 0, j = 3; while(i < j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } swaps characters correctly using two pointers; others overwrite or assign incorrectly.

3. Final Answer:

   int i = 0, j = 3; while(i < j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } -> Option D

4. Quick Check:

   Swap ends moving inward reverses string [OK]

Hint: Swap characters from ends moving inward [OK]

Common Mistakes:

• Overwriting characters without swapping
• Assigning string literal to array variable
• Ignoring null terminator in loops