java - StringBuffer : is it O(1)? 上 insert(0, c) 操作的复杂度

Question

我知道 StringBuffer 的 append() 操作需要 O(1) 时间，并且与 String 连接相比，它避免了创建 String 对象的多个副本的开销。

insert(int offset, char c) 呢？

我需要反复调用这个操作，将新的字符一个一个倒序加入到StringBuffer对象中。例如，

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

在理想情况下，如果 StringBuffer 对象在内部看起来像一个字符链表，则每个 insert(0, c) 应该是 O(1)。我想确认是否真的如此。

Answer 1

StringBuffer 上的insert 操作是 O(n)。这是因为它必须移开最多 n 个字符，以便为要插入的元素腾出空间。

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

您可以通过不使用 insert 来解决这个问题。您可以按相反顺序迭代字母，然后调用 O(1) append 方法。

StringBuffer 类是AbstractStringBuilder 的子类，它定义了一个char[] 来保存字符。它使用 System.arraycopy 在调用 insert 时将现有字符移开。