1.1 Vetores Estáticos vs. Listas Dinâmicas

Em estruturas baseadas em vetores estáticos, os elementos ocupam posições contíguas e exigem uma dimensão máxima pré-fixada. A Lista Ligada (ou simplesmente encadeada) adota um paradigma de alocação dinâmica:

A classe No modela a unidade atômica da estrutura. Ela possui duas propriedades com encapsulamento completo: o dado inteiro (numero) e o ponteiro para o próximo nó (prox).

public class No {
    private int numero;
    private No prox;

    No() {
    }

    No(int numero) {
        this.numero = numero;
    }

    public int getNumero() {
        return numero;
    }

    public void setNumero(int numero) {
        this.numero = numero;
    }

    public No getProx() {
        return prox;
    }

    public void setProx(No prox) {
        this.prox = prox;
    }
}

A classe Lista isola o controle da estrutura. O construtor instancia o nó sentinela inicial, e o método inserirNoInicio realiza a inserção instantânea em tempo constante O(1):

public class Lista {
    private No inicio; // Nó sentinela — não armazena dado real

    public Lista() {
        this.inicio = new No(0); // Sentinela: valor ignorado, só guia o prox
    }

    // Inserção no início da lista (O(1))
    public void inserirNoInicio(int valor) {
        No novo = new No(valor);
        novo.setProx(inicio.getProx());
        inicio.setProx(novo);
    }

    // Percurso e exibição dos elementos
    public void imprimir() {
        No atual = inicio.getProx(); // Pula o sentinela
        while (atual != null) {
            System.out.print(atual.getNumero() + " -> ");
            atual = atual.getProx();
        }
        System.out.println("null");
    }
}

4.1 Inserção Ordenada (Crescente)

Para manter a lista ordenada sem precisar reordená-la posteriormente, o algoritmo inspeciona o valor do próximo elemento (atual.getProx().getNumero()). Ao encontrar um valor maior ou o final da lista, encaixa o novo nó na posição correta:

// Inserção mantendo a ordem crescente
public void inserirOrdenado(int valor) {
    No novo = new No(valor);
    No atual = inicio;

    // Avança enquanto o próximo nó existir e seu valor for menor que o novo
    while (atual.getProx() != null && atual.getProx().getNumero() < valor) {
        atual = atual.getProx();
    }

    // Encaixa o novo nó entre 'atual' e 'atual.getProx()'
    novo.setProx(atual.getProx());
    atual.setProx(novo);
}

4.2 Remoção por Salto de Ponteiros

A remoção busca o nó anterior ao elemento alvo. Ao localizá-lo, desconecta o elemento fazendo um salto direto para o sucessor através de atual.setProx(atual.getProx().getProx()):

// Remoção de nó por valor com salto de ponteiro
public boolean remover(int valor) {
    No atual = inicio;

    // Busca o nó anterior ao valor procurado
    while (atual.getProx() != null && atual.getProx().getNumero() != valor) {
        atual = atual.getProx();
    }

    // Se o elemento existe na lista, "pula" o nó removendo-o da cadeia
    if (atual.getProx() != null) {
        atual.setProx(atual.getProx().getProx());
        return true;
    }

    return false; // Valor não localizado
}

Por que o Nó Sentinela Simplifica a Remoção?

Graças ao nó sentinela inicio, mesmo quando o primeiro elemento útil da lista (ex: o 10) precisa ser removido, a variável atual aponta para o sentinela. Não é necessário nenhum bloco if (inicio == alvo) específico!

A classe executável App.java valida na prática as inserções desordenadas que resultam em uma lista perfeitamente ordenada, seguida da remoção do elemento intermediário:

public class App {
    public static void main(String[] args) {
        Lista lista = new Lista();

        System.out.println("--- 1. Inserção Ordenada de Elementos ---");
        lista.inserirOrdenado(30);
        lista.inserirOrdenado(10);
        lista.inserirOrdenado(50);
        lista.inserirOrdenado(20);
        
        // Impressão esperada: 10 -> 20 -> 30 -> 50 -> null
        System.out.print("Lista após inserções: ");
        lista.imprimir();

        System.out.println("\n--- 2. Remoção do Elemento 30 ---");
        boolean removido = lista.remover(30);
        System.out.println("Elemento 30 removido com sucesso? " + removido);

        // Impressão esperada: 10 -> 20 -> 50 -> null
        System.out.print("Lista após remoção: ");
        lista.imprimir();
    }
}

Sintetize as características arquiteturais entre armazenamento sequencial por índice e encadeamento dinâmico: