Lista ligada com cauda - remover da posição p

Aprenda a remover da posição p de uma lista ligada com cauda (tail)

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

Pelo fato da lista ligada com cauda não ter í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 com cauda, 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 com cauda, 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 ListaLigadaCauda ficará após esta alteração adicionando a novo atributo tamanho:

public class ListaLigadaCauda<T> {

    private Node<T> inicio;
    private Node<T> fim;
    private int tamanho;

    public ListaLigadaCauda() {
        inicio = null;
        fim = null;
        tamanho = 0;
    }

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

    public Node getFim() {
        return fim;
    }

}

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.

Devemos também atualizar o nó final da lista, onde ele referenciará o novo nó caso a lista esteja vazia, ou o nó contido em início caso exista um, 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) {
        if (inicio != null && inicio.getProximo() != null) {
            inicio = inicio.getProximo();
            if (tamanho <= 1) {
                fim = inicio;
            }
        } else {
            inicio = null;
            fim = 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 {
        Node<T> node = inicio;
        // encontra o nó onde a ser removido
        for (int pos = 1; pos != posicao; pos++) {
            node = node.getProximo();
        }
        node.setProximo(node.getProximo().getProximo());

        // caso removido na última posição, atualizamos o valor de fim
        if ((posicao + 1) == tamanho) {
            fim = node;
        }
    }

}

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 {
        Node<T> node = inicio;
        // encontra o nó onde a ser removido
        for (int pos = 1; pos != posicao; pos++) {
            node = node.getProximo();
        }
        node.setProximo(node.getProximo().getProximo());

        // caso removido na última posição, atualizamos o valor de fim
        if ((posicao + 1) == tamanho) {
            fim = node;
        }
    }

    tamanho--; // decrementa o tamanho da lista

}

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

public class ListaLigadaCauda<T> {

    private Node<T> inicio;
    private Node<T> fim;
    private int tamanho;

    public ListaLigadaCauda() {
        inicio = null;
        fim = null;
        tamanho = 0;
    }

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

    public Node getFim() {
        return fim;
    }

    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 {
            Node<T> node = inicio;
            // encontra o nó onde a ser removido
            for (int pos = 1; pos != posicao; pos++) {
                node = node.getProximo();
            }
            node.setProximo(node.getProximo().getProximo());

            // caso removido na última posição, atualizamos o valor de fim
            if ((posicao + 1) == tamanho) {
                fim = node;
            }
        }

        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.