Entrar Ainda não tem acesso?
Solucionado (ver solução)
Solucionado
(ver solução)
1
resposta

Como ficaria a remoção de um elemento no meio da lista?

Referente ao curso Estrutura de Dados: computação na prática com Java, no capítulo Listas Duplamente Ligadas e atividade Listas duplamente ligadas

por Luís Otávio Bernardo de Andrade
| 135.8k xp | 22 posts

Na aula o instrutor demonstrou a remoção do elemento utilizando uma lista duplamente ligada.

Mas como ficaria se eu quisesse remover um elemento utilizando uma lista ligada normal?

Na implementação que eu fiz, tive que percorrer a lista duas vezes. Na primeira para achar a célula anterior a posição, e na segunda para encontrar a célula que eu de fato preciso excluir.

Essa abordagem está correta? Posso afirmar então que a remoção de um elemento no meio de uma lista ligada simples tem complexidade de O(n*n), visto que tive que percorrer a lista 2x?

1 resposta
solução!
por Luís Otávio Bernardo de Andrade
| 135.8k xp | 22 posts

Correção

Obviamente, percorrer a lista duas vezes estava errado. Basta percorrer a lista uma vez até o elemento célula anterior a posição e buscar a próxima célula.

Meu código ficou assim: 

       if (position == 0) { 
            removeAtTheBeginning();
        } else {
            Node previousNode = get(position - 1);
            Node nodeToBeDeleted = previousNode.getNext();

            previousNode.setNext(nodeToBeDeleted.getNext());

            if (nodeToBeDeleted.getNext() == null) {
                this.lastNode = previousNode;
            }

            totalOfElements--;
        }