Complexity of insert(0, c) operation on StringBuffer: is it O(1)?

Question

I am aware that the append() operation for StringBuffer takes O(1) time and it avoids the overhead of creating multiple copies of String objects as compared to String concatenation.

What about insert(int offset, char c)?

I need to repeatedly call this operation so as to add in new characters one by one in a reversed order to the StringBuffer object. For example,

StringBuffer sb = new StringBuffer();
sb.insert(0, 'c');
sb.insert(0, 'b');
sb.insert(0, 'a');
System.out.println(sb.toString()); //prints out "abc";

In an ideal situation, each insert(0, c) is supposed to be O(1) if internally that StringBuffer object looks like a linked list of characters. I wish to confirm if this is really the case.

Answer 1

The insert operation on a StringBuffer is O(n). This is because it must shift up to n characters out of the way to make room for the element to be inserted.

"bc"
insert(0, 'a') => "_bc" => "abc"

You can get around this by not using insert. You can iterate the letters in the reverse order, and then you can call the O(1) append method.

The StringBuffer class is a subclass of AbstractStringBuilder, which defines a char[] to hold the characters. It uses System.arraycopy to move the existing characters out of the way on a call to insert.