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

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.

Jon Skeet
people
quotationmark

Well, it's an implementation detail - but I wouldn't expect it to be a linked list of characters. I'd expect it to be a char[] with a length, basically - like an ArrayList, but for characters. So inserting a character at the start of the buffer means copying all the rest of the data.

That's been the basis of every implementation I've seen - a linked list of characters would have huge memory (and allocation time) costs compared with the more common implementation. A list or tree structure comprising of references to portions of strings (see "rope") wouldn't have the same costs, but I haven't personally seen a Java implementation of java.lang.StringBuilder or java.lang.StringBuffer which uses ropes.

people

See more on this question at Stackoverflow