As mentioned in Exercise 5.38, repeated String concatenation can be expensive. Consequently, Java provides a StringBuilder class. A StringBuilder is somewhat like an ArrayList that stores unlimited characters. The StringBuilder allows one to easily add to the end, automatically expanding an internal character array (by doubling its capacity) as needed. In so doing, the cost of appending can be assumed to be proportional to the number of characters added to the StringBuilder (rather than the number of characters in the result). At any point, the StringBuilder can be used to construct a String. Figure 5.16 contains two methods that return Strings containing N xs. What is the running time of each method? Run the methods on various values of N to verify your answer.

Figure 5.16:

public static String makeLongString1( int N )

{

String result = "";

for( int i = 0; i < N; i++ )

result += "x";

return result;

}

public static String makeLongString2( int N )

{

StringBuilder result = new StringBuilder( "" );

for( int i = 0; i < N; i++ )

result.append( "x" );

return new String( result );

}