Complexidade da operação de inserção (0, c) no StringBuffer: é O (1)?

Estou ciente de que a operação append () para StringBuffer leva O (1) tempo e evita a sobrecarga de criar várias cópias de objects String, em comparação com a concatenação de String.

E quanto a inserir (int offset, char c)?

Eu preciso chamar repetidamente essa operação para adicionar novos caracteres um por um em uma ordem inversa ao object StringBuffer. Por exemplo,

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

Em uma situação ideal, cada inserção (0, c) deve ser O (1) se internamente esse object StringBuffer se parece com uma linked list de caracteres. Desejo confirmar se esse é realmente o caso.

Bem, é um detalhe de implementação – mas eu não esperaria que fosse uma lista interligada de caracteres. Eu esperaria que fosse um char[] com comprimento, basicamente – como uma ArrayList , mas para caracteres. Portanto, inserir um caractere no início do buffer significa copiar todo o restante dos dados.

Essa tem sido a base de todas as implementações que eu vi – uma lista interligada de caracteres teria enormes custos de memory (e tempo de alocação) em comparação com a implementação mais comum. Uma lista ou estrutura de tree composta de referências a partes de strings (veja “corda” ) não teria os mesmos custos, mas eu pessoalmente não vi uma implementação Java de java.lang.StringBuilder ou java.lang.StringBuffer que usa cordas.

A operação de insert em um StringBuffer é O (n). Isso ocorre porque ele deve deslocar até n caracteres para abrir espaço para o elemento a ser inserido.

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

Você pode contornar isso não usando insert . Você pode iterar as letras na ordem inversa e, em seguida, pode chamar o método O (1) append .

A class StringBuffer é uma subclass de AbstractStringBuilder , que define um char[] para conter os caracteres. Ele usa System.arraycopy para mover os caracteres existentes fora do caminho em uma chamada para insert .

Eu não consegui encontrá-lo na documentação, mas provavelmente não é O (1), porque um StringBuffer internamente mantém um buffer char[] . Portanto, para uma seqüência de n caracteres, o tempo total necessário para essas operações é O (n ^ 2), já que cada insert(0, c) requer a troca de todo o conteúdo atual por 1.

Uma maneira mais eficiente de fazer isso seria apenas acrescentar todos os caracteres usando o append e, no final, usar sb.reverse() . A complexidade geral para isso é O (n) – O (1) amortizado para cada append e O (n) para o reverso.

Além disso, a menos que você tenha vários encadeamentos acessando seu StringBuffer , convém substituí-lo por um StringBuilder .

Bem, a estrutura de dados internos de StringBuilder é uma matriz e não um nó ligando para outros nós (lista ligada), então a resposta é não – não será 0 (1)