Doubly linked list

Lista duplamente encadeada

Cada nó guarda duas referências: next para o próximo nó e prev para o nó anterior.

nullptr ← prev · next → nullptr

Invariantes das pontas

  • head.prev é nullptr.
  • tail.next é nullptr.
  • Se A.next aponta para B, então B.prev deve apontar para A.
  • Na lista vazia, head e tail são nullptr.

Vantagem e custo

É possível percorrer nos dois sentidos e remover um nó conhecido sem procurar seu anterior.

Em troca, cada nó ocupa espaço para duas referências e cada alteração deve preservar as ligações dos dois lados.

Laboratório: prev e next

As setas e os campos precisam concordar. Ao remover uma ponta, o novo head ou tail também deve perder a referência para o nó que saiu.

Push e pop nas duas pontas

Operação
Ordem do head ao tail

    Custos com head e tail

    OperaçãoCustoCondição
    push_front / pop_frontO(1)Head é mantido.
    push_back / pop_backO(1)Tail é mantido e tail.prev encontra o penúltimo.
    Remover um nó conhecidoO(1)A referência do nó já foi fornecida.
    Encontrar o nó por valor ou posiçãoO(n)É necessário percorrer a lista.
    Detalhe importante: “remoção O(1)” não inclui o custo de procurar o nó. Se primeiro for preciso encontrá-lo, a operação completa continua O(n).

    Removendo um nó conhecido

    Os vizinhos passam a apontar um para o outro. Os casos de head e tail atualizam as referências externas da lista.

    C++17reconexão dos vizinhos
    #include <memory>

class ListaDupla {
    struct No {
        int valor;
        No* anterior = nullptr;
        std::unique_ptr<No> proximo;
        explicit No(int valor) : valor(valor) {}
    };

    std::unique_ptr<No> inicio;
    No* fim = nullptr;

public:
    void inserir_fim(int valor) {
        auto novo = std::make_unique<No>(valor);
        novo->anterior = fim;
        No* endereco = novo.get();

        if (fim) fim->proximo = std::move(novo);
        else inicio = std::move(novo);

        fim = endereco;
    }

    void percorrer_reverso() const {
        for (No* atual = fim; atual; atual = atual->anterior)
            std::cout << atual->valor << ' ';
    }
};

    Referências usadas