Conceitos e operações em listas encadeadas – Prof. Felipe Túlio de Castro

Conteúdo da página

Uma lista é uma estrutura de dados utilizada para armazenar uma sequência de elementos. Diferentemente de um vetor, em que os elementos ocupam posições indexadas e normalmente contíguas na memória, uma lista encadeada organiza seus elementos por meio de referências entre eles. Cormen et al. (2012) definem que “uma lista ligada é uma estrutura de dados na qual os objetos estão organizados em ordem linear”.

Essa organização torna as listas especialmente adequadas para conjuntos dinâmicos, isto é, situações em que elementos precisam ser incluídos e removidos durante a execução do programa. A ordem dos elementos não é determinada por índices, mas pelos ponteiros armazenados em cada elemento da estrutura (Cormen et al., 2012). Ziviani (2007) também destaca que a escolha da estrutura de dados está diretamente relacionada às operações que deverão ser realizadas sobre os dados.

Neste artigo, será utilizada como exemplo uma aplicação de lista de tarefas (em inglês, To Do List). Cada elemento armazenará a descrição de uma tarefa, como “Estudar listas encadeadas” ou “Resolver exercícios”.

O que é uma lista encadeada?

Uma lista encadeada é composta por elementos conectados entre si. Cada elemento armazena um dado e pelo menos um ponteiro que indica onde está localizado outro elemento da lista.

Enquanto um vetor pode ser representado conceitualmente como:

     0             1           2
[ Tarefa A ] [ Tarefa B ] [ Tarefa C ]

uma lista simplesmente encadeada pode ser representada como:

[inicio]
   |
   v
+-----------+     +-----------+     +-----------+
| Tarefa A  | --> | Tarefa B  | --> | Tarefa C  | --> nullptr
+-----------+     +-----------+     +-----------+

A principal característica dessa estrutura é que os elementos não precisam estar armazenados lado a lado na memória. A ligação lógica entre eles é estabelecida pelos ponteiros.

Essa forma de representação é apropriada para estruturas dinâmicas porque os elementos podem ser criados conforme a necessidade do programa. Em C++, isso pode ser feito com alocação dinâmica utilizando new, enquanto a liberação da memória pode ser realizada com delete.

Segundo Cormen et al. (2012), listas encadeadas fornecem uma representação simples e flexível para conjuntos dinâmicos. Martins (2009) também apresenta listas dinâmicas simplesmente e duplamente encadeadas como formas de implementar estruturas cujo número de elementos pode variar durante a execução.

Para entendermos a ideia de implementação das listas, precisamos compreender o conceito de nó. Ele é o elemento fundamental de uma lista encadeada e um nó armazena normalmente duas informações: um dado e um ponteiro.

+----------------------+----------------+
| dado                 | ponteiro       |
+----------------------+----------------+
| "Estudar ponteiros"  | próximo -----> |
+----------------------+----------------+

No exemplo da lista de tarefas, o dado será uma string contendo a descrição da tarefa.

Em C++, um nó de uma lista simplesmente encadeada pode ser definido assim:

struct NoSimples {
    string tarefa;
    NoSimples* proximo;
};

O campo tarefa contém o dado armazenado. O campo proximo contém o endereço do próximo nó. Se proximo possuir o valor nullptr, significa que não existe outro elemento depois daquele nó. Consequentemente, ele é o último elemento da lista.

Em listas dinâmicas, cada nó pode ser criado individualmente. Essa abordagem corresponde à ideia de que um Tipo Abstrato de Dados pode ser implementado por diferentes estruturas concretas, mantendo operações bem definidas sobre os elementos armazenados (Ziviani, 2007).

Lista simplesmente encadeada

Na lista simplesmente encadeada, cada nó possui apenas uma referência para o elemento seguinte.

inicio
  |
  v
+------------+    +------------+    +------------+
| Tarefa A   | -> | Tarefa B   | -> | Tarefa C   |
+------------+    +------------+    +------------+
                                         |
                                         v
                                      nullptr

Assim, o percurso ocorre naturalmente em uma única direção:

início → próximo → próximo → ... → fim

Cormen et al. (2012) explicam que, em uma lista simplesmente ligada, o ponteiro para o elemento anterior é omitido. Por isso, a estrutura ocupa menos espaço por nó que uma lista duplamente encadeada, embora determinadas operações possam exigir mais percurso.

Lista duplamente encadeada

Na lista duplamente encadeada, cada nó armazena dois ponteiros:

anterior
próximo

Sua estrutura pode ser visualizada assim:

nullptr <- [Tarefa A] <-> [Tarefa B] <-> [Tarefa C] -> nullptr
              ^
              |
            inicio

Cada nó conhece tanto seu sucessor quanto seu predecessor.

Em C++, criaremos a estrutura da seguinte forma:

struct NoDuplo {
    string tarefa;
    NoDuplo* anterior;
    NoDuplo* proximo;
};

A vantagem é permitir percursos nas duas direções:

início → fim

fim → início

Porém, a desvantagem é o consumo adicional de memória, pois cada nó precisa armazenar dois ponteiros.

Percurso em uma lista

Percorrer uma lista significa visitar seus nós sucessivamente.

Em uma lista simplesmente encadeada, normalmente criamos um ponteiro auxiliar:

NoSimples* atual = inicio;

Em seguida, avançamos enquanto houver elementos:

while (atual != nullptr) {
    cout << atual->tarefa << endl;
    atual = atual->proximo;
}

O funcionamento pode ser visualizado assim:

atual
  |
  v
[Tarefa A] -> [Tarefa B] -> [Tarefa C] -> nullptr

                atual
                  |
                  v
[Tarefa A] -> [Tarefa B] -> [Tarefa C] -> nullptr

                              atual
                                |
                                v
[Tarefa A] -> [Tarefa B] -> [Tarefa C] -> nullptr

Esse mecanismo é importante porque operações como busca, remoção por valor e inserção no final frequentemente dependem do percurso da estrutura.

Inserção no início

Inserir no início é uma das operações mais simples em uma lista encadeada. Considere:

inicio
  |
  v
[Tarefa B] -> [Tarefa C]

Desejamos inserir:

Tarefa A

Primeiramente, o novo nó aponta para o antigo início:

[Tarefa A] ------+
                 |
                 v
              [Tarefa B] -> [Tarefa C]

Depois, inicio passa a apontar para o novo nó:

inicio
  |
  v
[Tarefa A] -> [Tarefa B] -> [Tarefa C]

Essa operação pode ser realizada sem percorrer a lista. Por isso, sua complexidade é O(1).

Em uma lista simplesmente encadeada:

void inserirInicio(NoSimples*& inicio, const string& tarefa) {
    NoSimples* novo = new NoSimples{tarefa, inicio};
    inicio = novo;
}

Observe que inicio é recebido por referência porque a função pode modificar o endereço do primeiro elemento da lista.

Inserção no final

Inserir no final exige encontrar o último elemento quando a estrutura mantém apenas o ponteiro para o início. Considere:

[Tarefa A] -> [Tarefa B] -> nullptr

Queremos inserir:

Tarefa C

Primeiramente percorremos a lista até:

[Tarefa B]

Depois modificamos seu ponteiro:

[Tarefa A] -> [Tarefa B] -> [Tarefa C] -> nullptr

Sem um ponteiro específico para o último nó, essa operação possui complexidade O(n). Entretanto, se a estrutura mantiver um ponteiro chamado fim, a inserção pode ser realizada diretamente em O(1). Essa é uma decisão de projeto importante, pois informações adicionais podem acelerar determinadas operações ao custo de um pouco mais de memória e de maior cuidado na atualização dos ponteiros.

Busca de uma tarefa

A busca em uma lista encadeada normalmente é sequencial. Suponha a seguinte busca:

"Revisar ponteiros"
        |
        v
"Estudar listas"
        |
        v
"Resolver exercícios"

Para localizar "Estudar listas", começamos no primeiro nó:

Revisar ponteiros

Como não corresponde ao valor procurado, avançamos:

Estudar listas

O elemento foi encontrado.

Uma implementação simples para este caso seria:

NoSimples* buscar(NoSimples* inicio, const string& tarefa) {
    NoSimples* atual = inicio;

    while (atual != nullptr) {
        if (atual->tarefa == tarefa) {
            return atual;
        }

        atual = atual->proximo;
    }

    return nullptr;
}

Se a função retornar nullptr, a tarefa não está presente.

Remoção por valor

A remoção exige cuidado porque um nó faz parte de uma cadeia. Considere que temos a seguinte lista:

[Tarefa A] -> [Tarefa B] -> [Tarefa C]

e desejamos remover:

Tarefa B

Não podemos simplesmente apagar o nó:

[Tarefa A]    [Tarefa C]

Antes disso, precisamos fazer Tarefa A apontar para Tarefa C:

[Tarefa A] ----------------------> [Tarefa C]
                 [Tarefa B]

e só depois o nó pode ser liberado da memória:

delete removido;

Então, o resultado será:

[Tarefa A] -> [Tarefa C]

Complexidade das principais operações

Para as implementações apresentadas neste artigo, podemos resumir as complexidades assim:

Operação	Lista simplesmente encadeada	Lista duplamente encadeada
Inserir no início	O(1)	O(1)
Inserir no final sem ponteiro `fim`	O(n)	O(n)
Inserir no final mantendo `fim`	O(1)	O(1)
Buscar por valor	O(n)	O(n)
Remover por valor	O(n)	O(n)
Percorrer do início ao fim	O(n)	O(n)
Percorrer do fim ao início	Não diretamente	O(n)

Observe que, embora a lista duplamente encadeada possua mais informações estruturais, ela não torna automaticamente a busca por valor mais rápida. Se não houver outra estrutura de indexação, ainda será necessário percorrer os elementos.

Implementação de uma lista de tarefas

O código a seguir reúne os conceitos apresentados até este ponto. Nele, há duas estruturas independentes: uma lista simplesmente encadeada e uma lista duplamente encadeada. O programa utiliza apenas recursos fundamentais de C++ e foi mantido propositalmente simples para favorecer a compreensão do funcionamento dos ponteiros.

#include <iostream>
#include <string>

using namespace std;

// ======================================================
// LISTA SIMPLESMENTE ENCADEADA
// ======================================================

struct NoSimples {
    string tarefa;
    NoSimples* proximo;
};

void inserirInicio(NoSimples*& inicio, const string& tarefa) {
    NoSimples* novo = new NoSimples{tarefa, inicio};
    inicio = novo;
}

void inserirFim(NoSimples*& inicio, const string& tarefa) {
    NoSimples* novo = new NoSimples{tarefa, nullptr};

    if (inicio == nullptr) {
        inicio = novo;
        return;
    }

    NoSimples* atual = inicio;

    while (atual->proximo != nullptr) {
        atual = atual->proximo;
    }

    atual->proximo = novo;
}

NoSimples* buscar(NoSimples* inicio, const string& tarefa) {
    NoSimples* atual = inicio;

    while (atual != nullptr) {
        if (atual->tarefa == tarefa) {
            return atual;
        }

        atual = atual->proximo;
    }

    return nullptr;
}

bool removerPorValor(NoSimples*& inicio, const string& tarefa) {
    if (inicio == nullptr) {
        return false;
    }

    // O elemento procurado é o primeiro da lista.
    if (inicio->tarefa == tarefa) {
        NoSimples* removido = inicio;

        inicio = inicio->proximo;

        delete removido;

        return true;
    }

    NoSimples* atual = inicio;

    /*
     * Procuramos o nó anterior ao elemento que
     * será removido.
     */
    while (
        atual->proximo != nullptr &&
        atual->proximo->tarefa != tarefa
    ) {
        atual = atual->proximo;
    }

    if (atual->proximo == nullptr) {
        return false;
    }

    NoSimples* removido = atual->proximo;

    atual->proximo = removido->proximo;

    delete removido;

    return true;
}

void exibir(NoSimples* inicio) {
    NoSimples* atual = inicio;

    while (atual != nullptr) {
        cout << "- " << atual->tarefa << endl;
        atual = atual->proximo;
    }
}

void liberar(NoSimples*& inicio) {
    while (inicio != nullptr) {
        NoSimples* removido = inicio;

        inicio = inicio->proximo;

        delete removido;
    }
}

// ======================================================
// LISTA DUPLAMENTE ENCADEADA
// ======================================================

struct NoDuplo {
    string tarefa;

    NoDuplo* anterior;
    NoDuplo* proximo;
};

void inserirInicio(
    NoDuplo*& inicio,
    NoDuplo*& fim,
    const string& tarefa
) {
    NoDuplo* novo = new NoDuplo{
        tarefa,
        nullptr,
        inicio
    };

    if (inicio != nullptr) {
        inicio->anterior = novo;
    } else {
        fim = novo;
    }

    inicio = novo;
}

void inserirFim(
    NoDuplo*& inicio,
    NoDuplo*& fim,
    const string& tarefa
) {
    NoDuplo* novo = new NoDuplo{
        tarefa,
        fim,
        nullptr
    };

    if (fim != nullptr) {
        fim->proximo = novo;
    } else {
        inicio = novo;
    }

    fim = novo;
}

NoDuplo* buscar(
    NoDuplo* inicio,
    const string& tarefa
) {
    NoDuplo* atual = inicio;

    while (atual != nullptr) {
        if (atual->tarefa == tarefa) {
            return atual;
        }

        atual = atual->proximo;
    }

    return nullptr;
}

bool removerPorValor(
    NoDuplo*& inicio,
    NoDuplo*& fim,
    const string& tarefa
) {
    NoDuplo* removido = buscar(inicio, tarefa);

    if (removido == nullptr) {
        return false;
    }

    /*
     * Liga o elemento anterior
     * ao próximo elemento.
     */
    if (removido->anterior != nullptr) {
        removido->anterior->proximo =
            removido->proximo;
    } else {
        inicio = removido->proximo;
    }

    /*
     * Liga o próximo elemento
     * ao elemento anterior.
     */
    if (removido->proximo != nullptr) {
        removido->proximo->anterior =
            removido->anterior;
    } else {
        fim = removido->anterior;
    }

    delete removido;

    return true;
}

void exibir(NoDuplo* inicio) {
    NoDuplo* atual = inicio;

    while (atual != nullptr) {
        cout << "- " << atual->tarefa << endl;
        atual = atual->proximo;
    }
}

void exibirReverso(NoDuplo* fim) {
    NoDuplo* atual = fim;

    while (atual != nullptr) {
        cout << "- " << atual->tarefa << endl;
        atual = atual->anterior;
    }
}

void liberar(
    NoDuplo*& inicio,
    NoDuplo*& fim
) {
    while (inicio != nullptr) {
        NoDuplo* removido = inicio;

        inicio = inicio->proximo;

        delete removido;
    }

    fim = nullptr;
}

// ======================================================
// PROGRAMA PRINCIPAL
// ======================================================

int main() {

    cout << "LISTA SIMPLESMENTE ENCADEADA" << endl;

    NoSimples* listaSimples = nullptr;

    inserirInicio(
        listaSimples,
        "Revisar ponteiros"
    );

    inserirFim(
        listaSimples,
        "Estudar listas encadeadas"
    );

    inserirFim(
        listaSimples,
        "Resolver exercicios"
    );

    exibir(listaSimples);

    string procurada =
        "Estudar listas encadeadas";

    if (
        buscar(listaSimples, procurada)
        != nullptr
    ) {
        cout
            << "Tarefa encontrada: "
            << procurada
            << endl;
    }

    removerPorValor(
        listaSimples,
        "Revisar ponteiros"
    );

    cout << "\nApos a remocao:" << endl;

    exibir(listaSimples);

    liberar(listaSimples);

    cout
        << "\nLISTA DUPLAMENTE ENCADEADA"
        << endl;

    NoDuplo* inicio = nullptr;
    NoDuplo* fim = nullptr;

    inserirInicio(
        inicio,
        fim,
        "Preparar ambiente C++"
    );

    inserirFim(
        inicio,
        fim,
        "Implementar lista de tarefas"
    );

    inserirFim(
        inicio,
        fim,
        "Testar operacoes da lista"
    );

    cout
        << "Percurso do inicio para o fim:"
        << endl;

    exibir(inicio);

    cout
        << "\nPercurso do fim para o inicio:"
        << endl;

    exibirReverso(fim);

    removerPorValor(
        inicio,
        fim,
        "Implementar lista de tarefas"
    );

    cout << "\nApos a remocao:" << endl;

    exibir(inicio);

    liberar(inicio, fim);

    return 0;
}

Uma possível saída do programa que você verá no terminal é:

LISTA SIMPLESMENTE ENCADEADA
- Revisar ponteiros
- Estudar listas encadeadas
- Resolver exercicios
Tarefa encontrada: Estudar listas encadeadas

Apos a remocao:
- Estudar listas encadeadas
- Resolver exercicios

LISTA DUPLAMENTE ENCADEADA
Percurso do inicio para o fim:
- Preparar ambiente C++
- Implementar lista de tarefas
- Testar operacoes da lista

Percurso do fim para o inicio:
- Testar operacoes da lista
- Implementar lista de tarefas
- Preparar ambiente C++

Apos a remocao:
- Preparar ambiente C++
- Testar operacoes da lista

Entendendo a remoção na lista simplesmente encadeada

Um dos trechos mais importantes do exemplo anterior é:

NoSimples* removido = atual->proximo;

atual->proximo = removido->proximo;

delete removido;

Suponha:

atual
  |
  v
[A] -> [B] -> [C]
        ^
        |
     removido

Neste momento:

removido = atual->proximo;

faz removido apontar para B.

Depois:

atual->proximo = removido->proximo;

faz A apontar diretamente para C:

[A] ---------> [C]

       [B]

Finalmente:

delete removido;

libera a memória ocupada por B. Nesta caso, o resultado se torna:

[A] -> [C]

Lembre-se que esse é um dos princípios fundamentais da manipulação de estruturas encadeadas. Então, primeiro corrigimos os encadeamentos e somente depois liberamos o nó removido.

Entendendo a remoção na lista duplamente encadeada

Na lista duplamente encadeada, considere:

[A] <-> [B] <-> [C]

Para retirar B, são necessários dois ajustes.

Primeiro:

removido->anterior->proximo = removido->proximo;

faz A apontar para C.

Depois:

removido->proximo->anterior = removido->anterior;

faz C apontar novamente para A.

O resultado passa a ser:

[A] <-> [C]

Lista simplesmente ou duplamente encadeada?

A escolha depende das operações necessárias. Uma lista simplesmente encadeada tende a ser adequada quando o percurso sempre ocorre em uma direção e se deseja uma estrutura mais simples, com menos ponteiros. A lista duplamente encadeada é particularmente útil quando a aplicação precisa navegar para frente e para trás ou quando a relação entre sucessores e predecessores precisa ser acessada diretamente.

Em uma aplicação de tarefas, por exemplo, uma lista simplesmente encadeada pode ser suficiente para percorrer as tarefas pendentes em sequência. Uma lista duplamente encadeada poderia ser interessante se a interface permitisse navegar entre a tarefa anterior e a próxima.

Conclusão

Listas encadeadas são estruturas fundamentais para compreender armazenamento dinâmico, ponteiros e relacionamento entre objetos em memória.

Na lista simplesmente encadeada, cada nó referencia apenas seu sucessor. Na lista duplamente encadeada, cada nó mantém referências tanto para o sucessor quanto para o predecessor. Em ambos os casos, operações como inserção, remoção e busca dependem principalmente da correta manipulação dos ponteiros.

O domínio dessas estruturas também serve como fundamento para tópicos posteriores de Estruturas de Dados, pois princípios de encadeamento aparecem em filas dinâmicas, pilhas dinâmicas, tabelas hash, grafos e outras estruturas.

Obrigado pela leitura e bons estudos!

Referências

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.

MARTINS, Paulo Roberto (org.). Algoritmos e estrutura de dados: análise e desenvolvimento de sistemas. São Paulo: Pearson Prentice Hall, 2009.

ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Java e C++. São Paulo: Thomson Learning, 2007.