StringBuffer上insert（0，c）操作的复杂性：它是O（1）吗？
我知道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对象内部看起来像链接的字符列表，则每个插入（0，c）应该是O（1）。 我想确认是否真的如此。
嗯，这是一个实现细节 – 但我不希望它是一个链接的字符列表。 我希望它是一个有长度的char[] ，基本上 – 就像一个ArrayList ，但是对于字符。 因此，在缓冲区的开头插入一个字符意味着复制所有其余的数据。
这是我见过的每个实现的基础 – 与更常见的实现相比，链接的字符列表将具有巨大的内存（和分配时间）成本。 包含对字符串部分的引用的列表或树结构（参见“rope” ）将不会有相同的成本，但我没有亲自看过使用java.lang.StringBuilder或java.lang.StringBuffer的Java实现。绳索。
StringBuffer上的insert操作是O（n）。 这是因为它必须最多移动n字符以便为要插入的元素腾出空间。
"bc" insert(0, 'a') => "_bc" => "abc"
你可以通过不使用insert来解决这个问题。 您可以按相反的顺序迭代字母，然后可以调用O（1） append方法。
StringBuffer类是AbstractStringBuilder的子类，它定义了一个用于保存字符的char[] 。 它使用System.arraycopy在insert调用时insert现有字符移开。
我在文档中找不到它，但它很可能不是O（1），因为StringBuffer内部维护一个char[]缓冲区。 因此，对于n字符的序列，这些操作所需的总时间是O（n ^ 2），因为每个insert(0, c)需要将所有当前内容移位1。
更有效的方法是使用append附加所有字符，最后使用sb.reverse() 。 其总体复杂度为O（n） – 每个append分摊O（1），反向O（n）。
此外，除非您有多个线程访问您的StringBuffer ，否则您可能需要考虑将其替换为StringBuilder 。
那么StringBuilder的内部数据结构是一个数组，而不是链接到其他节点（链表）的节点，所以答案是否定的 – 它不会是0（1）