Implement StringBuilder

I was asked this in an interview yesterday. I could add whatever methods, members and constructors I wanted but I couldn't change the signature of the provided toString and append methods.

I implemented something like this:

import java.util.ArrayList;
import java.util.List;

public class StringBuilder {

  private List characterBuffer;

  public StringBuilder() {
    characterBuffer = new ArrayList();
  }

  public void append(String anotherString) {
    if(anotherString != null) {
      char[] charArray = anotherString.toCharArray();
      for(int i=0;i<charArray.length; i++) {
        characterBuffer.add(charArray[i]);
      }
    }
  }

  public String toString() {
    char[] charArray = new char[characterBuffer.size()];
    for(int i=0; i<charArray.length; i++) {
      charArray[i] = characterBuffer.get(i);
    }
    return new String(charArray);
  }

}

When asked if there was another approach I might have taken, I suggested using a primitive char array buffer that can grow if there is an overflow. Not liking to leave things unfinished, I implemented this solution when I got home:

import java.util.Arrays;

public class StringBuilder {

  private char[] characterBuffer;
  private int curIndex;

  public StringBuilder() {
    characterBuffer = new char[5];
    curIndex = 0;
  }

  public void append(String anotherString) {
    if(anotherString != null) {
      char[] charArray = anotherString.toCharArray();
      int charArrayLength = charArray.length;
      if(overflow(charArrayLength)) {
        characterBuffer = Arrays.copyOf(characterBuffer, newLength(charArrayLength));
      } 
      for(int i=0;i characterBuffer.length;
  }

  public String toString() {
    return new String(characterBuffer, 0, curIndex);
  }

}

I'd like both approaches reviewed.

I'm concentration on performance as it's the sole reason for the existence of StringBuilder (otherwise a String would do).

private List characterBuffer;

This is obviously very inefficient. List is fine, but converting every char in Character surely is not. The memory consumption is bad, too, namely 4 or 8 bytes (depending on using compressed oops) for the reference and 0 or 8 bytes for the object (0 if it's a cached Character, i.e., ASCII). So you need 4 to 16 bytes per char instead of 2.

public StringBuilder() {
    characterBuffer = new ArrayList();
}

This should be done in the initializer.

if(anotherString != null) {

There should be a space after if. Silently ignoring null is strange (not that appending "null" would be any better).

char[] charArray = anotherString.toCharArray();

This is needlessly inefficient as you're creating a throw-away charArray while you can use anotherString.charAt instead.

An interesting approach would be to collect the given strings instead. If your string builder gets fed mostly with strings, collecting them as they come could be better than flattening them into a single char[]. While this would make some operations (e.g., delete) pretty complicated, it could be pretty efficient for the most important operations.


I suggested using a primitive char array buffer that can grow if there is an overflow.

That's the standard approach.

private int curIndex;

Let's call it length as it's what length() returns.

public StringBuilder() {
    characterBuffer = new char[5];
    curIndex = 0;
}

The former belongs to the initializer, the latter belongs nowhere (it's the default).

if(overflow(charArrayLength)) {

A method checking for overflow is fine, but a method handling it would be better.

private int newLength(int arrayLength) {
    return (characterBuffer.length + arrayLength) + 10;
}

No! You'll be resizing too often. Imagine appending "0123456789A" in a loop. Every single append will copy the whole buffer, more and more characters... complexity \$O(n^2)\$.

What you need is an exponential growth. Something like

2 * characterBuffer.length + arrayLength + 10;

or

characterBuffer.length + (characterBuffer.length >> 1) + arrayLength + 10;

if you want a growth factor of 1.5.

private boolean overflow(int arrayLength) {
    return (arrayLength + curIndex) > characterBuffer.length;
}

Needless parens. I guess, it should read >=.

StackExchange Code Review Q#73526, answer score: 6