Implement StringBuilder

Question

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<Character> characterBuffer;

  public StringBuilder() {
    characterBuffer = new ArrayList<Character>();
  }

  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<charArray.length; i++) {
        characterBuffer[curIndex++] = charArray[i];
      }
    }
  }

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

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

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

}

I'd like both approaches reviewed.

Answer 1

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

---

private List<Character> 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<Character>();
}

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 >=.

Answer 2

Using a list for this purpose is not ergonomic, which is very noticeable in the toString implementations of your two approaches (the second one is spot-on). For a reasonably fast solution, a char[] is clearly the way to go.

No need to name it characterBuffer, you don't normally put the type's name in the name. So buffer is nice and simple for this purpose. A StringBuilder implementation will probably not need any other kind of buffer anyway.

As @maaartinus pointed out, the biggest problem in both of your implementations is the throw-away char[] allocations. Be careful with that, it's a big mistake.

Perhaps the approach they were looking for is the technique taken by the JDK's StringBuilder implementation: using String.getChars to copy characters from a source string to a target char[] at some offset and with some length, like this:

    if (str == null) str = "null";
    int len = str.length();
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;

Now that looks unbeatable in terms of performance.