Uma lista encadeada simples é uma estrutura de dados linear onde cada elemento (nó) contém um valor e uma referência para o próximo nó na sequência. Neste artigo, exploramos as operações fundamentais dessa estrutura, sem o uso de nó sentinela (nó cabeça fictício).

Definição da Estrutura em C

Iniciamos definindo um apelido para o tipo de dados armazenado e a estrutura do nó:

typedef int TipoDado;
typedef struct NoLista {
    TipoDado valor;
    struct NoLista* proximo;
} No;

Criação de um Novo Nó

A função abaixo aloca dinamicamente um novo nó, atribui o valor fornecido e inicializa o ponteiro para o próximo como nulo:

No* criar_no(TipoDado v) {
    No* novo = (No*)malloc(sizeof(No));
    if (novo == NULL) {
        fprintf(stderr, "Falha na alocacao de memoria\n");
        exit(EXIT_FAILURE);
    }
    novo->valor = v;
    novo->proximo = NULL;
    return novo;
}

Exibição da Lista

Para percorrer e imprimir todos os elementos, basta iterar a partir do ponteiro inicial até encontrar um nó nulo:

void exibir_lista(No* inicio) {
    No* atual = inicio;
    while (atual != NULL) {
        printf("[%d] -> ", atual->valor);
        atual = atual->proximo;
    }
    printf("NULL\n");
}

Inserção no Final

Para inserir um elemento no final da lista, criamos um novo nó e o posicionamos após o último nó existente. Caso a lista esteja vazia, o novo nó se torna o primeiro:

void inserir_fim(No** cabeca, TipoDado v) {
    No* novo = criar_no(v);
    if (*cabeca == NULL) {
        *cabeca = novo;
        return;
    }
    No* cursor = *cabeca;
    while (cursor->proximo != NULL) {
        cursor = cursor->proximo;
    }
    cursor->proximo = novo;
}

Observe que utilizamos um ponteiro duplo (No**) como parâmetro. Isso é necessário porque, quando a lista está vazia, precisamos modificar o próprio ponteiro que aponta para o primeiro nó. Passar apenas um ponteiro simples resultaria em uma cópia local, e alterações não afetariam o ponteiro original no chamador.

Inserção no Início

A inserção no início é mais direta: o novo nó aponta para o antigo primeiro elemento, e o ponteiro da cabeça é atualizado:

void inserir_inicio(No** cabeca, TipoDado v) {
    No* novo = criar_no(v);
    novo->proximo = *cabeca;
    *cabeca = novo;
}

Remoção do Final

A remoção do último nó exige encontrar o penúltimo elemento. Tratamos dois casos: quando há apenas um nó e quando há múltiplos nós:

void remover_fim(No** cabeca) {
    assert(*cabeca != NULL);

    // Caso: apenas um nó na lista
    if ((*cabeca)->proximo == NULL) {
        free(*cabeca);
        *cabeca = NULL;
        return;
    }

    // Caso: dois ou mais nós — navegar até o penúltimo
    No* anterior = *cabeca;
    while (anterior->proximo->proximo != NULL) {
        anterior = anterior->proximo;
    }
    free(anterior->proximo);
    anterior->proximo = NULL;
}

Remoção do Início

Para remover o primeiro nó, salvamos a referência ao segundo nó antes de liberar a memória do primeiro:

void remover_inicio(No** cabeca) {
    assert(*cabeca != NULL);
    No* temporario = *cabeca;
    *cabeca = temporario->proximo;
    free(temporario);
}

Busca por Valor

A função de busca percorre a lista e retorna um ponteiro para o nó que contém o valor procurado, ou NULL caso não encontre:

No* buscar_valor(No* inicio, TipoDado alvo) {
    No* cursor = inicio;
    while (cursor != NULL) {
        if (cursor->valor == alvo)
            return cursor;
        cursor = cursor->proximo;
    }
    return NULL;
}

É possível utilizar essa função para localizar múltiplas ocorrências, passando o ponteiro do próximo nó a cada iteração:

/* Exemplo de busca por múltiplas ocorrências:
No* resultado = buscar_valor(cabeca, 5);
int contador = 1;
while (resultado != NULL) {
    printf("Ocorrencia %d encontrada no endereco %p com valor %d\n",
           contador++, (void*)resultado, resultado->valor);
    resultado = buscar_valor(resultado->proximo, 5);
}
*/

Inserção Após um Nó Específico

Inserir um novo nó logo após um determinaod nó é uma operação eficiente, pois não requer percorrer a lista. Basta ajustar os ponteiros:

void inserir_apos(No* referencia, TipoDado v) {
    assert(referencia != NULL);
    No* novo = criar_no(v);
    novo->proximo = referencia->proximo;
    referencia->proximo = novo;
}

Inserção Antes de um Nó Específico

Para inserir antes de um nó, é necessário percorrer a lista até encontrar o nó anterior ao alvo. Tratamos separadamente o caso em que o nó alvo é o primeiro:

void inserir_antes(No** cabeca, No* alvo, TipoDado v) {
    assert(alvo != NULL);
    No* novo = criar_no(v);

    if (*cabeca == alvo) {
        novo->proximo = *cabeca;
        *cabeca = novo;
        return;
    }

    No* anterior = *cabeca;
    while (anterior != NULL && anterior->proximo != alvo) {
        anterior = anterior->proximo;
    }
    if (anterior != NULL) {
        anterior->proximo = novo;
        novo->proximo = alvo;
    }
}

Remoção de um Nó Específico

Ao remover um nó, precisamos atualizar o ponteiro do nó anterior para apontar ao sucessor do nó removido:

void remover_no(No** cabeca, No* alvo) {
    assert(cabeca != NULL && *cabeca != NULL && alvo != NULL);

    if (*cabeca == alvo) {
        remover_inicio(cabeca);
        return;
    }

    No* anterior = *cabeca;
    while (anterior != NULL && anterior->proximo != alvo) {
        anterior = anterior->proximo;
    }
    if (anterior != NULL) {
        anterior->proximo = alvo->proximo;
        free(alvo);
    }
}

Liberação Completa da Memória

Para destruir toda a lista e evitar vazamentos de memória, percorremos cada nó, salvamos o próximo e liberamos o atual:

void destruir_lista(No** cabeca) {
    No* atual = *cabeca;
    while (atual != NULL) {
        No* proximo = atual->proximo;
        free(atual);
        atual = proximo;
    }
    *cabeca = NULL;
}

Considerações sobre Ponteiro Duplo

Nesta implementação, sem nó sentinela, operações como inserção no início, inserção antes de um nó e remoção do primeiro elemento requerem o uso de ponteiro duplo (No**). Isso ocorre porque essas operações podem modificar o ponteiro que aponta para o primeiro nó da lista. Se utilizássemos um nó sentinela (nó cabeça fictício), essas operações poderiam ser simplificadas, pois o nó sentinela nunca seria removido — bastaria manipular seus campos de ponteiro.

Implementação em Python

Abaixo segue uma implementação equivalente em Python, mantendo a semântica da lista encadeada simples:

class NoEncadeado:
    """Representa um único nó da lista encadeada."""
    __slots__ = ('valor', 'proximo')

    def __init__(self, valor):
        self.valor = valor
        self.proximo = None


class ListaEncadeada:
    """Implementação de lista encadeada simples sem nó sentinela."""

    def __init__(self):
        self._inicio = None
        self._tamanho = 0

    @property
    def tamanho(self):
        return self._tamanho

    def esta_vazia(self):
        return self._tamanho == 0

    def inserir_no_fim(self, valor):
        novo = NoEncadeado(valor)
        if self._inicio is None:
            self._inicio = novo
        else:
            ponteiro = self._inicio
            while ponteiro.proximo is not None:
                ponteiro = ponteiro.proximo
            ponteiro.proximo = novo
        self._tamanho += 1

    def inserir_no_inicio(self, valor):
        novo = NoEncadeado(valor)
        novo.proximo = self._inicio
        self._inicio = novo
        self._tamanho += 1

    def remover_do_fim(self):
        if self._inicio is None:
            raise IndexError("Lista vazia")
        if self._inicio.proximo is None:
            valor_removido = self._inicio.valor
            self._inicio = None
        else:
            atual = self._inicio
            while atual.proximo.proximo is not None:
                atual = atual.proximo
            valor_removido = atual.proximo.valor
            atual.proximo = None
        self._tamanho -= 1
        return valor_removido

    def remover_do_inicio(self):
        if self._inicio is None:
            raise IndexError("Lista vazia")
        valor_removido = self._inicio.valor
        self._inicio = self._inicio.proximo
        self._tamanho -= 1
        return valor_removido

    def buscar(self, valor):
        atual = self._inicio
        while atual is not None:
            if atual.valor == valor:
                return atual
            atual = atual.proximo
        return None

    def inserir_apos(self, no_referencia, valor):
        if no_referencia is None:
            raise ValueError("Nó de referência inválido")
        novo = NoEncadeado(valor)
        novo.proximo = no_referencia.proximo
        no_referencia.proximo = novo
        self._tamanho += 1

    def remover_no(self, no_alvo):
        if self._inicio is None or no_alvo is None:
            raise ValueError("Operação inválida")
        if self._inicio is no_alvo:
            self._inicio = no_alvo.proximo
        else:
            anterior = self._inicio
            while anterior is not None and anterior.proximo is not no_alvo:
                anterior = anterior.proximo
            if anterior is None:
                raise ValueError("Nó não pertence à lista")
            anterior.proximo = no_alvo.proximo
        self._tamanho -= 1

    def __iter__(self):
        atual = self._inicio
        while atual is not None:
            yield atual.valor
            atual = atual.proximo

    def __str__(self):
        elementos = []
        ponteiro = self._inicio
        while ponteiro is not None:
            elementos.append(str(ponteiro.valor))
            ponteiro = ponteiro.proximo
        return " -> ".join(elementos) + " -> None"

    def limpar(self):
        self._inicio = None
        self._tamanho = 0

Na implementação em Python, não há necessidade de ponteiro duplo, pois os objetos são acessados por referência. Ao atribuir self._inicio = novo, a alteração é refletida diretamente na instância da lista.