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.
Eu preciso chamar repetidamente essa operação para adicionar novos caracteres um por um em uma ordem inversa ao object StringBuffer. Por exemplo,
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.
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.