Java CharAt() and deleteCharAt() performance

Question

I've been wondering about the implementation of charAt function for String/StringBuilder/StringBuffer in java what is the complexity of that ? also what about the deleteCharAt() in StringBuffer/StringBuilder ?

Answer 1

For String, StringBuffer, and StringBuilder, charAt() is a constant-time operation.

For StringBuffer and StringBuilder, deleteCharAt() is a linear-time operation.

StringBuffer and StringBuilder have very similar performance characteristics. The primary difference is that the former is synchronized (so is thread-safe) while the latter is not.

Answer 2

Let us just look at the corresponding actual java implementation(only relevant code) for each of these methods in turn. That itself will answer about their efficiency.

String.charAt :

public char charAt(int index) {     if ((index < 0) || (index >= value.length)) {         throw new StringIndexOutOfBoundsException(index);     }     return value[index]; } 

As we can see, it is just a single array access which is a constant time operation.

StringBuffer.charAt :

public synchronized char charAt(int index) {   if ((index < 0) || (index >= count))     throw new StringIndexOutOfBoundsException(index);   return value[index]; } 

Again, single array access, so a constant time operation.

StringBuilder.charAt :

public char charAt(int index) {     if ((index < 0) || (index >= count))         throw new StringIndexOutOfBoundsException(index);     return value[index]; } 

Again, single array access, so a constant time operation. Even though all these three methods look same, there are some minor differences. For example, only StringBuffer.charAt method is synchronized but not other methods. Similarly if check is slightly different for String.charAt (guess why?). Closer look at these method implementations itself give us other minor differences among them.

Now, let us look at deleteCharAt implementations.

String does not have deleteCharAt method. The reason might be it is an immutable object. So exposing an API which explicitly indicates that this method modifies the object is not probably a good idea.

Both StringBuffer and StringBuilder are subclasses of AbstractStringBuilder. The deleteCharAt method of these two classes is delegating the implementation to its parent class itself.

StringBuffer.deleteCharAt :

  public synchronized StringBuffer deleteCharAt(int index) {         super.deleteCharAt(index);         return this;     } 

StringBuilder.deleteCharAt :

 public StringBuilder deleteCharAt(int index) {         super.deleteCharAt(index);         return this;     } 

AbstractStringBuilder.deleteCharAt :

  public AbstractStringBuilder deleteCharAt(int index) {         if ((index < 0) || (index >= count))             throw new StringIndexOutOfBoundsException(index);         System.arraycopy(value, index+1, value, index, count-index-1);         count--;         return this;     } 

A closer look at AbstractStringBuilder.deleteCharAt method reveals that it is actually calling System.arraycopy. This can be O(N) in worst case. So deleteChatAt method is O(N) time complexity.