Olá, pessoal!
Não é a primeira vez que tenho uma dúvida com relação a listas simplesmente encadeadas.
Por que a complexidade de inserção no final da lista é constante [O(1)], enquanto para remoção no final é n [O(n)] ?
Para inserir, o último item aponta para o novo último item. Esse novo ultimo item aponta para null.
Para remover, não seria ir direto para o último item, pegar o penúltimo e fazê-lo apontar para null e depois apagar o antigo último item?
Alguém me exclareça, por favor!
[quote=ECO2004]Olá, pessoal!
Não é a primeira vez que tenho uma dúvida com relação a listas simplesmente encadeadas.
Por que a complexidade de inserção no final da lista é constante [O(1)], enquanto para remoção no final é n [O(n)] ?
Para inserir, o último item aponta para o novo último item. Esse novo ultimo item aponta para null.
Para remover, não seria ir direto para o último item, pegar o penúltimo e fazê-lo apontar para null e depois apagar o antigo último item?
Alguém me exclareça, por favor![/quote]
Eu mesmo solucionei o problema…rs
Só para deixar resposta: Eu tenho que encontrar o penútimo item para fazê-lo apontar para null. Eu tenho o último item, mas para a lista simplesmente encadeada anda somente para um lado - para frente. Ela não consegue “voltar”. Assim, para encontrar tal penúltimo item, ela deve percorrer todo o vetor até achá-lo.
Por isso, complexidade n [O(n)].