Java Data Structures and Algorithms for Beginners

Mutable Strings

Definition and Concepts

Mutable strings in Java refer to string-like data structures that can be modified after creation, unlike the immutable String class. Java provides two primary classes for mutable strings: StringBuilder and StringBuffer. Both classes allow operations like appending, inserting, or deleting characters without creating new objects, making them efficient for text manipulation. StringBuilder is designed for single-threaded environments, offering better performance, while StringBuffer is thread-safe, suitable for multi-threaded applications. You can visualize a mutable string as a dynamic sequence of characters that can be altered in place, such as changing "Hello" to "Hello World" by appending characters directly. Mutable strings are essential for performance-critical applications requiring frequent text modifications.

Why Use It?

Mutable strings are used to efficiently manipulate text in scenarios where frequent modifications, such as appending or inserting characters, are needed. Unlike immutable String objects, which create new instances for each operation, StringBuilder and StringBuffer modify their internal character arrays, reducing memory overhead and improving performance. StringBuilder is preferred for single-threaded applications due to its speed, while StringBuffer is used when thread safety is required. These classes are ideal for building strings incrementally, such as in loops or dynamic text generation.

Where to Use? (Real-Life Examples)

• Log Message Construction: Logging frameworks use StringBuilder to construct log messages by appending data, avoiding the overhead of multiple String concatenations.
• Text File Generation: Report generators use StringBuilder to build large text outputs, such as CSV or JSON files, by incrementally adding content.
• String Manipulation in Editors: Text editors use mutable strings to handle user edits, such as inserting or deleting text in a document, in real-time.
• Thread-Safe Text Processing: Multi-threaded server applications use StringBuffer to build responses concurrently, ensuring thread safety during string modifications.

Explain Operations

• Append: This operation adds characters, strings, or other data types to the end of the mutable string. It has a time complexity of O(1) amortized.
• Insert: This operation inserts characters or strings at a specified index, shifting subsequent characters. It has a time complexity of O(n) due to shifting.
• Delete: This operation removes a range of characters from the mutable string, shifting remaining characters. It has a time complexity of O(n) due to shifting.
• Replace: This operation replaces a range of characters with a new string. It has a time complexity of O(n) due to shifting and copying.
• Length: This operation returns the number of characters in the mutable string. It has a time complexity of O(1).

Java Implementation

The following Java code demonstrates common operations using StringBuilder and StringBuffer.

public class MutableStringExamples {
    // StringBuilder Append: Appends a string to a StringBuilder
    public StringBuilder appendStringBuilder(StringBuilder builder, String str) {
        return builder.append(str); // Appends str to the builder
    }

    // StringBuilder Insert: Inserts a string at a specified index
    public StringBuilder insertStringBuilder(StringBuilder builder, int index, String str) {
        if (index < 0 || index > builder.length()) {
            throw new IllegalArgumentException("Invalid index.");
        }
        return builder.insert(index, str); // Inserts str at the specified index
    }

    // StringBuilder Delete: Deletes a range of characters
    public StringBuilder deleteStringBuilder(StringBuilder builder, int start, int end) {
        if (start < 0 || end > builder.length() || start > end) {
            throw new IllegalArgumentException("Invalid start or end index.");
        }
        return builder.delete(start, end); // Deletes characters from start to end-1
    }

    // StringBuilder Replace: Replaces a range of characters
    public StringBuilder replaceStringBuilder(StringBuilder builder, int start, int end, String str) {
        if (start < 0 || end > builder.length() || start > end) {
            throw new IllegalArgumentException("Invalid start or end index.");
        }
        return builder.replace(start, end, str); // Replaces characters from start to end-1 with str
    }

    // StringBuilder Length: Returns the number of characters
    public int getLengthStringBuilder(StringBuilder builder) {
        return builder.length(); // Returns the current length
    }

    // StringBuffer Example: Demonstrates thread-safe append
    public StringBuffer appendStringBuffer(StringBuffer buffer, String str) {
        return buffer.append(str); // Appends str to the thread-safe buffer
    }
}

How It Works

1. Append:
   • The appendStringBuilder method calls builder.append(str) to add str to the end of the StringBuilder’s internal character array.
   • For example, appendStringBuilder(new StringBuilder("Hello"), " World") results in "Hello World".
   • The appendStringBuffer method works similarly for StringBuffer with thread-safe synchronization.
2. Insert:
   • The insertStringBuilder method calls builder.insert(index, str) to insert str at the specified index, shifting subsequent characters.
   • For example, insertStringBuilder(new StringBuilder("Hlo"), 1, "el") results in "Hello".
3. Delete:
   • The deleteStringBuilder method calls builder.delete(start, end) to remove characters from start to end-1, shifting remaining characters.
   • For example, deleteStringBuilder(new StringBuilder("Hello"), 1, 4) results in "Ho".
4. Replace:
   • The replaceStringBuilder method calls builder.replace(start, end, str) to replace characters from start to end-1 with str.
   • For example, replaceStringBuilder(new StringBuilder("Halo"), 1, 3, "el") results in "Hello".
5. Length:
   • The getLengthStringBuilder method calls builder.length() to return the number of characters.
   • For example, getLengthStringBuilder(new StringBuilder("Hello")) returns 5.

Complexity Analysis Table

Note:

• n is the length of the mutable string or the resulting string after the operation.
• Append is O(1) amortized due to occasional resizing of the internal array.
• Space complexity accounts for the internal character array, which may resize dynamically.

Key Differences / Notes

• StringBuilder vs. StringBuffer:
  • StringBuilder is not thread-safe but faster, making it suitable for single-threaded applications.
  • StringBuffer is thread-safe due to synchronized methods, making it slower but appropriate for multi-threaded environments.
• Mutable vs. Immutable Strings:
  • Unlike the immutable String class, which creates new objects for modifications, StringBuilder and StringBuffer modify their internal arrays, reducing memory overhead.
  • Operations like concatenation with String have O(n) space complexity per operation, while StringBuilder/StringBuffer appends are more efficient.
• Internal Array Resizing: Both classes use a dynamic array that doubles in size when capacity is exceeded, leading to O(1) amortized append time but occasional O(n) resizing.
• Java’s String Pool: Mutable strings (StringBuilder/StringBuffer) are not stored in the string pool, unlike String literals. Converting to String via toString() creates a new String that may be interned into the pool if needed.

✅ Tip: Use StringBuilder for most mutable string operations in single-threaded applications to maximize performance. Reserve StringBuffer for scenarios requiring thread safety, such as concurrent server applications.

⚠ Warning: Avoid using StringBuilder in multi-threaded environments without synchronization, as it can lead to data corruption. Use StringBuffer or explicit synchronization for thread-safe string manipulation.

Exercises

1. String Reversal: Write a Java program that reverses a string using StringBuilder and StringBuffer. Compare their performance for large inputs.
2. Dynamic Text Builder: Create a program that builds a formatted string (e.g., a CSV row) using StringBuilder, appending elements from an array. Test with varying array sizes.
3. Thread-Safe Concatenation: Implement a multi-threaded program that uses StringBuffer to append strings concurrently from multiple threads. Verify thread safety with test cases.
4. Insert and Delete Simulation: Write a program that simulates text editing using StringBuilder, performing a sequence of insert and delete operations. Test with different sequences.
5. StringBuilder Capacity Management: Create a program that demonstrates StringBuilder’s capacity resizing by appending strings and monitoring capacity changes using capacity(). Analyze when resizing occurs.