Inner classes and implementation of ArrayList - Data Structures and Problem Solving Using Java - page 584

StringBuilder

15.4

Figure 15.12 also shows a respectable linear-time implementation of toString ,
using a StringBuilder to avoid quadratic running time. ( StringBuilder was added
in Java 5 and is slightly faster than StringBuffer ; it is preferable for single-
threaded applications). To see why StringBuilder is needed, consider the
following code fragment that builds a String with N A 's:

String result = "";
for( int i = 0; i < N; i++ )
result += 'A';

While there is no doubt that this fragment works correctly because String
objects are immutable, each call to result += 'A' is rewritten as result =
result + 'A' , and once we see that, it is apparent that each String concatena-
tion creates a new String object. As we get further into the loop, these String
objects become more expensive to create. We can estimate the cost of the i th
String concatenation to be i , so the total cost is 1 + 2 + 3 + ... + N , or O ( N 2 ). If
N is 100,000, it is simple to write the code and see that the running time is
significant. Yet a simple rewrite

char [ ] theChars = new char[ N ];
for( int i = 0; i < N; i++ )
theChars[ i ] = 'A';
String result = new String( theChars );

results in a linear-time algorithm that executes in the blink of the eye.
The use of an array of characters works only if we know the final size of
the String . Otherwise, we have to use something like ArrayList<char> . A
StringBuilder is similar in concept to an ArrayList<char> , with array dou-
bling but with method names that are specific for String operations. Using a
StringBuilder , the code looks like

StringBuilder sb = new StringBuilder( );
for( int i = 0; i < N; i++ )
sb.append( 'A' );
String result = new String( sb );

This code is linear-time and runs quickly. Some String concatenations,
such as those in a single expression, are optimized by the compiler to
avoid repeated creations of String s. But if your concatenations are inter-
mingled with other statements, as is the case here, then you often can use
a StringBuilder for more efficient code.