Prática de Listas Encadeadas

#include <iostream>
#include <stdexcept>
#include <vector>

class Pilha {
private:
    std::vector<int> dados;

public:
    bool vazia() const { return dados.empty(); }
    std::size_t tamanho() const { return dados.size(); }

    void empilhar(int valor) {
        dados.push_back(valor); // O fim do vetor é o topo.
    }

    int topo() const {
        if (vazia()) throw std::runtime_error("pilha vazia");
        return dados.back();
    }

    int desempilhar() {
        int removido = topo();  // topo também valida o estado.
        dados.pop_back();
        return removido;
    }
};

int main() {
    Pilha pilha;
    pilha.empilhar(10);
    pilha.empilhar(20);
    pilha.empilhar(30);

    std::cout << pilha.desempilhar() << '\n'; // 30
    std::cout << pilha.topo() << '\n';        // 20
    std::cout << pilha.tamanho() << '\n';     // 2
}

Invariante: somente o último elemento pode ser removido. As operações principais têm custo amortizado O(1).

#include <iostream>
#include <stdexcept>

class PilhaEncadeada {
    struct No {
        int valor;
        No* proximo;
    };

    No* topo_ = nullptr;

public:
    ~PilhaEncadeada() {
        while (!vazia()) desempilhar();
    }

    bool vazia() const { return topo_ == nullptr; }

    void empilhar(int valor) {
        topo_ = new No{valor, topo_};
    }

    int desempilhar() {
        if (vazia()) throw std::runtime_error("pilha vazia");
        No* removido = topo_;
        int valor = removido->valor;
        topo_ = removido->proximo;
        delete removido;
        return valor;
    }

    int topo() const {
        if (vazia()) throw std::runtime_error("pilha vazia");
        return topo_->valor;
    }
};

int main() {
    PilhaEncadeada p;
    p.empilhar(4);
    p.empilhar(9);
    std::cout << p.desempilhar() << ' ' << p.topo() << '\n';
}

Memória: cada new possui um delete correspondente. O destrutor libera os nós que permanecerem na pilha.

#include <iostream>
#include <stdexcept>

class Fila {
    struct No { int valor; No* proximo; };
    No* inicio = nullptr;
    No* fim = nullptr;

public:
    ~Fila() { while (!vazia()) desenfileirar(); }
    bool vazia() const { return inicio == nullptr; }

    void enfileirar(int valor) {
        No* novo = new No{valor, nullptr};
        if (vazia()) inicio = fim = novo;
        else {
            fim->proximo = novo;
            fim = novo;
        }
    }

    int desenfileirar() {
        if (vazia()) throw std::runtime_error("fila vazia");
        No* removido = inicio;
        int valor = removido->valor;
        inicio = inicio->proximo;
        if (inicio == nullptr) fim = nullptr;
        delete removido;
        return valor;
    }
};

int main() {
    Fila fila;
    fila.enfileirar(7);
    fila.enfileirar(8);
    fila.enfileirar(9);
    std::cout << fila.desenfileirar() << '\n'; // 7
}

Invariante: fila vazia significa inicio == nullptr e fim == nullptr.

#include <array>
#include <iostream>
#include <stdexcept>

class FilaCircular {
    static constexpr int capacidade = 5;
    std::array<int, capacidade> dados{};
    int inicio = 0;
    int fim = 0;       // Próxima posição livre.
    int quantidade = 0;

public:
    bool vazia() const { return quantidade == 0; }
    bool cheia() const { return quantidade == capacidade; }

    void enfileirar(int valor) {
        if (cheia()) throw std::runtime_error("fila cheia");
        dados[fim] = valor;
        fim = (fim + 1) % capacidade;
        ++quantidade;
    }

    int desenfileirar() {
        if (vazia()) throw std::runtime_error("fila vazia");
        int valor = dados[inicio];
        inicio = (inicio + 1) % capacidade;
        --quantidade;
        return valor;
    }
};

int main() {
    FilaCircular fila;
    for (int valor : {10, 20, 30, 40}) fila.enfileirar(valor);
    std::cout << fila.desenfileirar() << '\n';
    fila.enfileirar(50); // Pode reutilizar uma posição do início.
}

Vantagem: nenhuma remoção desloca elementos. Inserção e remoção permanecem O(1).

#include <iostream>
#include <stdexcept>

class Deque {
    struct No { int valor; No* anterior; No* proximo; };
    No* inicio = nullptr;
    No* fim = nullptr;

    int remover(No* no, bool peloInicio) {
        if (!no) throw std::runtime_error("deque vazio");
        int valor = no->valor;
        if (inicio == fim) inicio = fim = nullptr;
        else if (peloInicio) {
            inicio = inicio->proximo;
            inicio->anterior = nullptr;
        } else {
            fim = fim->anterior;
            fim->proximo = nullptr;
        }
        delete no;
        return valor;
    }

public:
    ~Deque() { while (inicio) removerInicio(); }

    void inserirInicio(int valor) {
        No* novo = new No{valor, nullptr, inicio};
        if (inicio) inicio->anterior = novo;
        else fim = novo;
        inicio = novo;
    }

    void inserirFim(int valor) {
        No* novo = new No{valor, fim, nullptr};
        if (fim) fim->proximo = novo;
        else inicio = novo;
        fim = novo;
    }

    int removerInicio() { return remover(inicio, true); }
    int removerFim() { return remover(fim, false); }
};

int main() {
    Deque d;
    d.inserirInicio(20);
    d.inserirInicio(10);
    d.inserirFim(30);
    std::cout << d.removerInicio() << ' ' << d.removerFim() << '\n';
}

Complexidade: todas as quatro operações nas extremidades são O(1).

#include <iostream>

class ListaSimples {
    struct No { int valor; No* proximo; };
    No* inicio = nullptr;
    No* fim = nullptr;

public:
    ~ListaSimples() {
        while (inicio) {
            No* removido = inicio;
            inicio = inicio->proximo;
            delete removido;
        }
    }

    void inserirInicio(int valor) {
        inicio = new No{valor, inicio};
        if (fim == nullptr) fim = inicio;
    }

    void inserirFim(int valor) {
        No* novo = new No{valor, nullptr};
        if (fim) fim->proximo = novo;
        else inicio = novo;
        fim = novo;
    }

    void exibir() const {
        for (No* atual = inicio; atual; atual = atual->proximo)
            std::cout << atual->valor << ' ';
        std::cout << '\n';
    }
};

int main() {
    ListaSimples lista;
    lista.inserirFim(20);
    lista.inserirInicio(10);
    lista.inserirFim(30);
    lista.exibir(); // 10 20 30
}

Invariante: se a lista estiver vazia, início e fim são nulos; caso contrário, fim->proximo é nulo.

#include <iostream>

class Lista {
    struct No { int valor; No* proximo; };
    No* inicio = nullptr;
    No* fim = nullptr;

public:
    ~Lista() { while (inicio) remover(inicio->valor); }

    void inserirFim(int valor) {
        No* novo = new No{valor, nullptr};
        if (fim) fim->proximo = novo;
        else inicio = novo;
        fim = novo;
    }

    bool contem(int valor) const {
        for (No* atual = inicio; atual; atual = atual->proximo)
            if (atual->valor == valor) return true;
        return false;
    }

    bool remover(int valor) {
        No* anterior = nullptr;
        No* atual = inicio;
        while (atual && atual->valor != valor) {
            anterior = atual;
            atual = atual->proximo;
        }
        if (!atual) return false;

        if (anterior) anterior->proximo = atual->proximo;
        else inicio = atual->proximo;
        if (fim == atual) fim = anterior;
        delete atual;
        return true;
    }
};

int main() {
    Lista lista;
    for (int valor : {5, 8, 13}) lista.inserirFim(valor);
    std::cout << lista.contem(8) << '\n';
    lista.remover(8);
    std::cout << lista.contem(8) << '\n';
}

Complexidade: busca e remoção por valor custam O(n), pois talvez seja necessário percorrer toda a lista.

#include <iostream>

class ListaDupla {
    struct No { int valor; No* anterior; No* proximo; };
    No* inicio = nullptr;
    No* fim = nullptr;

public:
    ~ListaDupla() {
        while (inicio) {
            No* removido = inicio;
            inicio = inicio->proximo;
            delete removido;
        }
    }

    void inserirFim(int valor) {
        No* novo = new No{valor, fim, nullptr};
        if (fim) fim->proximo = novo;
        else inicio = novo;
        fim = novo;
    }

    void exibirDireto() const {
        for (No* p = inicio; p; p = p->proximo)
            std::cout << p->valor << ' ';
        std::cout << '\n';
    }

    void exibirReverso() const {
        for (No* p = fim; p; p = p->anterior)
            std::cout << p->valor << ' ';
        std::cout << '\n';
    }
};

int main() {
    ListaDupla lista;
    for (int valor : {10, 20, 30}) lista.inserirFim(valor);
    lista.exibirDireto();
    lista.exibirReverso();
}

Custo: os dois percursos são O(n). A ligação anterior permite voltar sem reconstruir o caminho.

#include <iostream>
#include <vector>

void mostrar(const std::vector<int>& valores) {
    for (int valor : valores) std::cout << valor << ' ';
    std::cout << '\n';
}

void insertionSort(std::vector<int>& valores) {
    for (std::size_t i = 1; i < valores.size(); ++i) {
        int chave = valores[i];
        std::size_t j = i;

        while (j > 0 && valores[j - 1] > chave) {
            valores[j] = valores[j - 1]; // Desloca, não troca.
            --j;
        }
        valores[j] = chave;
        mostrar(valores);
    }
}

int main() {
    std::vector<int> valores{7, 3, 9, 2, 5};
    insertionSort(valores);
}

Complexidade: melhor caso O(n); pior caso O(n²); espaço auxiliar O(1).

#include <iostream>
#include <string>

struct Produto {
    int codigo;
    std::string nome;
};

class Catalogo {
    struct No { Produto produto; No* proximo; };
    No* inicio = nullptr;

public:
    ~Catalogo() {
        while (inicio) remover(inicio->produto.codigo);
    }

    void inserir(Produto produto) {
        No** posicao = &inicio;
        while (*posicao && (*posicao)->produto.codigo < produto.codigo)
            posicao = &((*posicao)->proximo);

        *posicao = new No{std::move(produto), *posicao};
    }

    bool remover(int codigo) {
        No** posicao = &inicio;
        while (*posicao && (*posicao)->produto.codigo != codigo)
            posicao = &((*posicao)->proximo);
        if (!*posicao) return false;

        No* removido = *posicao;
        *posicao = removido->proximo;
        delete removido;
        return true;
    }

    void listar() const {
        for (No* p = inicio; p; p = p->proximo)
            std::cout << p->produto.codigo << " - "
                      << p->produto.nome << '\n';
    }
};

int main() {
    Catalogo catalogo;
    catalogo.inserir({30, "Teclado"});
    catalogo.inserir({10, "Mouse"});
    catalogo.inserir({20, "Monitor"});
    catalogo.remover(20);
    catalogo.listar(); // 10 antes de 30.
}

Técnica: o ponteiro para ponteiro permite alterar tanto inicio quanto um campo proximo usando o mesmo algoritmo.