Lista ligada - remover da posição p

Aprenda a remover da posição p de uma lista ligada

Remover elementos em uma posição p é uma tarefa um pouco mais complexa e que requer três etapas.

Pelo fato da lista ligada não tem índices, teremos que percorrer a lista para encontrar o nó que desejamos remover, fazendo as referências entre eles de modo correto.

O processo para remover um elemento na posição p pode ser dividido em três etapas.

A primeira delas é verificar se o índice é válido, pois a posição p onde iremos remover o novo elemento não pode ser maior do que o tamanho da lista.

A segunda parte consiste no caso especial onde a posição a qual desejamos remover o nó é a posição 0, pois neste caso não precisaremos percorrer a lista sendo que temos acesso ao nó inicial dela diretamente na lista ligada, bastanto apenas configurar corretamente a sua referência.

A terceira etapa consiste em percorrer a lista até a posição correta, e após isso alterar a sua referência.

Para implementar a primeira etapa, onde devemos validar se a posição p é válida, precisamos do tamanho da lista, o que pode ser custoso pois teremos que percorrer a lista para descobrir o seu tamanho.

Pensando em otimizar este processo, vamos fazer uma pequena alteração na nossa classe da lista ligada, adicionando a ela um contador (int tamanho) que é incrementado e decrementado sempre que adicionamos ou removemos um elemento da lista, respectivamente.

Isto fará com que a obtenção do tamanho seja simplificada a verificação de uma variável.

Veja a seguir como a classe ListaLigada ficará após esta alteração adicionando a novo atributo tamanho:

public class ListaLigada<T> {

    private Node<T> inicio;
    private int tamanho;

    public ListaLigada() {
        inicio = null;
        tamanho = 0;
    }

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

}

Com essa alteração, conseguimos implementar de modo otimizado a validação da posição p.

Vamos a seguir demonstrar como implementar este algoritmo de modo de modo gradual, passo a passo.

A seguir temos a declaração do método e a implementação da validação da posição p, onde caso ela seja inválida lançamos uma exception, conforme o código a seguir:

public void remover(int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }
}

Na sequência adicionamos a este método o caso especial para quando a posição é zero, pois neste caso devemos referênciar o próximo nó na posição inicial caso ele exista, ou somente definir o nó inicial como null caso a lista possua no máximo um único elemento, ficando conforme o código a seguir:

public void remover(int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }

    if (posicao == 0) {
        // caso a lista possua mais de um nó,
        // define o segundo nó como o nó inicial da lista
        if (inicio != null && inicio.getProximo() != null) {
            inicio = inicio.getProximo();
        } else {
            // caso contrário apenas o define como null
            inicio = null;
        }
    }

}

Com isso, o que resta agora é adicionar o código para percorrer a lista até encontrar a posição correta para a remoção, e fazer as referências corretas, conforme o código a seguir:

public void remover(int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }

    if (posicao == 0) {
        // caso a lista possua mais de um nó,
        // define o segundo nó como o nó inicial da lista
        if (inicio != null && inicio.getProximo() != null) {
            inicio = inicio.getProximo();
        } else {
            // caso contrário apenas o define como null
            inicio = null;
        }
    } else {
        // registra a posição atual
        int posicaoLista = 1;
        Node<T> node = inicio;
        // busca o node da posição p
        while (posicao != posicaoLista) {
            node = node.getProximo();
            posicaoLista++;
        }
        // define a referência corretamente
        node.setProximo(node.getProximo().getProximo());
    }

}

Repare que adicionamos este código como else no if existente, pois ele será executado para toda posição p válida e maior do que zero.

Para finalizar, precisamos decrementar o novo atributo tamanho que adicionamos na classe, pois assim conseguimos manter o seu tamanho atualizado.

A seguir temos o código completo do método:

public void remover(int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }

    if (posicao == 0) {
        // caso a lista possua mais de um nó,
        // define o segundo nó como o nó inicial da lista
        if (inicio != null && inicio.getProximo() != null) {
            inicio = inicio.getProximo();
        } else {
            // caso contrário apenas o define como null
            inicio = null;
        }
    } else {
        // registra a posição atual
        int posicaoLista = 1;
        Node<T> node = inicio;
        // busca o node da posição p
        while (posicao != posicaoLista) {
            node = node.getProximo();
            posicaoLista++;
        }
        // define a referência corretamente
        node.setProximo(node.getProximo().getProximo());
    }

    tamanho--; // decrementa o tamanho da lista

}

E para finalizar, vamor ver o novo método adicionado ao código da classe da lista ligada:

public class ListaLigada<T> {

    private Node<T> inicio;
    private int tamanho;

    public ListaLigada() {
        inicio = null;
        tamanho = 0;
    }

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

    public void remover(int posicao) {
        // posição deve ser maior do que 0 e menor do que o tamanho da lista
        if (posicao < 0 || posicao >= tamanho) {
            throw new IllegalArgumentException("Posição inválida");
        }

        if (posicao == 0) {
            // caso a lista possua mais de um nó,
            // define o segundo nó como o nó inicial da lista
            if (inicio != null && inicio.getProximo() != null) {
                inicio = inicio.getProximo();
            } else {
                // caso contrário apenas o define como null
                inicio = null;
            }
        } else {
            // registra a posição atual
            int posicaoLista = 1;
            Node<T> node = inicio;
            // busca o node da posição p
            while (posicao != posicaoLista) {
                node = node.getProximo();
                posicaoLista++;
            }
            // define a referência corretamente
            node.setProximo(node.getProximo().getProximo());
        }

        tamanho--; // decrementa o tamanho da lista

    }

}

Com isso finalizamos a implementação do método para remover na lista na posição p, que embora ela possua mais passos, se estudado de modo separado fica simples de entender o processo de remoção na posição p.