Como ficaria a remoção de um elemento no meio da lista? | Estrutura de Dados: computação na prática com Java

Solucionado (ver solução)

Solucionado
(ver solução)

1
resposta

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

05/03/2021

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--;
        }