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)