Singly linked list

Lista simplesmente encadeada

É uma lista implementada por nós em que cada nó guarda um valor e uma referência para o próximo nó.

head → next → nullptr

Componentes

Node contém value e next.
head referencia o primeiro nó e dá acesso à lista.
tail é opcional; quando mantido, referencia o último nó.
O next do último nó vale nullptr.

Consequência da ligação única

É possível avançar seguindo next. Não existe um ponteiro direto para voltar ao nó anterior.

Para acessar o elemento da posição i, começamos no head e percorremos até essa posição: O(n) no pior caso.

Laboratório: IDs e referências

Os IDs deixam visível qual objeto cada next referencia. Após push ou pop, observe quais ligações mudam.

Alterações no head e no tail

Operação

Ordem alcançada pelo head

Custos com head e tail

Operação	Custo	Motivo
push_front	O(1)	O novo nó aponta para o head antigo.
pop_front	O(1)	Head passa a apontar para head.next.
push_back	O(1) com tail	Tail.next recebe o novo nó.
pop_back	O(n)	É necessário encontrar o penúltimo nó.
Acessar posição / buscar valor	O(n)	O percurso começa no head.
Inserir depois de um nó conhecido	O(1)	Somente referências locais são atualizadas.

Representação em C++

O ID usado no HTML não precisa existir como campo do objeto. No código real, a própria referência em next conecta os nós.

C++17nós e lista

#include <memory>

class ListaSimples {
    struct No {
        int valor;
        std::unique_ptr<No> proximo;
        explicit No(int valor) : valor(valor), proximo(nullptr) {}
    };

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

public:
    void inserir_inicio(int valor) {
        auto novo = std::make_unique<No>(valor);
        if (!fim) fim = novo.get();
        novo->proximo = std::move(inicio);
        inicio = std::move(novo);
    }

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

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

        fim = endereco;
    }
};

Referências usadas

NIST — list: coleção acessada sequencialmente do head ao tail.
NIST — linked list: cada item possui ligação para o próximo.