Listas ligadas simples em C++ (Parte I)

As listas ligadas são estruturas de dados que consistem num conjunto de nós ligados entre si. Existem vários tipos de listas ligadas, como, por exemplo: Listas ligadas simples, listas duplamente ligadas e listas circulares. De forma análoga aos arrays dinâmicos (ver artigos “Funções malloc e realloc em C / C++” e “Arrays dinâmicos com structs em C++“), as listas ligadas permitem introduzir tantos nós quanto a capacidade de memória do computador permitir, alocando memória à medida que vamos precisando de inserir novos nós. Vejamos vantagens e desvantagens dos usos das listas em comparação com arrays dinâmicos:

Vantagens:

• Inserir e remover elementos é mais simples e evita termos que andar a deslocar dados para a direita ou para a esquerda dentro de um array.
• A implementação de pilhas e filas torna-se mais simples com o uso de listas.
• Não precisam de ter um controlo de capacidade e do uso da função “realloc”.

Desvantagens:

• Não é possível aceder directamente a um determinado nó de uma lista, sendo necessária uma leitura sequencial dos nós até chegarmos ao nó pretendido. Normalmente temos apenas um apontador para a cabeça (início) da lista e, conforme a implementação, um apontador para a cauda (fim) da lista.
• As listas ocupam mais memória pois, para cada nó (ou elemento) temos que adicionar um apontador para o nó seguinte (listas ligadas simples) ou dois apontadores (listas duplamente ligadas).
• Os nós não estão contíguos em memória, o que torna o tempo de acesso relativamente mais lento.

Neste artigo, vou falar de listas ligadas simples. Para estas listas, precisamos de ter um apontador para a cabeça e, para cada nó, um apontador para o nó seguinte.

A figura seguinte ilustra uma lista de números inteiros:

A caixa mais pequena, no canto superior esquerdo, representa a cabeça da lista que aponta para o primeiro nó. Em cada nó, temos um apontador para o nó seguinte, até chegarmos ao último que deverá apontar para NULL (simbolizado com a barra “/”).

Vamos então começar com este exemplo simples, usando uma “struct” para representar um nó com um valor inteiro. Podemos então definir o nosso nó da seguinte forma:

struct No {
    int valor;
    No *seguinte;
};

E declaramos os seguintes apontadores:

    No *cabeca = NULL;
    No *no = NULL;

Em que o apontador “cabeca” será o nosso apontador para o início da lista e o apontador “no”, um apontador a ser usado para as nossas operações sobre a lista (por vezes iremos precisar de mais um, como veremos em alguns casos). Repare que a cabeça é inicializada a NULL, o que indica que a lista está vazia.

Para listarmos todos os valores da nossa lista, podemos escrever o seguinte código:

    if (cabeca==NULL) {
        cout << "A lista está vazia!" << endl;
    }
    else {
        no = cabeca;
        while (no!=NULL) {
            cout << "Valor: " << no->valor << endl;
            no = no->seguinte;
        }
    }

Neste exemplo, testamos primeiro se a lista está vazia (linha 1). Se tiver elementos, fazemos um ciclo “while” para listarmos os valores dos nós até chegarmos ao último nó (linha 6).

Para inserirmos valores na lista, podemos fazê-lo das seguintes formas:

Inserção à cabeça

Na figura acima, estamos a introduzir um nó com o valor 4220 à cabeça. Na figura mais acima, vimos que a cabeça apontava para o elemento com o valor 1234. Então, é necessário copiar o apontador da cabeça para o apontador do nó seguinte no novo nó com o valor 4220 e alterar o apontador da cabeça para este novo nó.

Vamos ver como podemos fazer tal através de código C++. Note que, no código, não sabemos se a lista ainda está vazia! Por isso, será necessário testar esta condição:

    no = (No*) malloc(sizeof(No));
    no->valor=4220;
    if (cabeca==NULL) {
        no->seguinte = NULL;
    }
    else {
        no->seguinte = cabeca;
    }
    cabeca = no;

Repare que, na linha 3, testamos se a cabeça está a NULL – o que indica que a lista está vazia – e, nesse caso, o apontador do nó seguinte deverá ser NULL, pois este será o primeiro e último (linha 4). Se a lista não estiver vazia, copia-se o apontador da cabeça para o nó seguinte (linha 7). Finalmente, a cabeça irá sempre passar a apontar para o novo nó (linha 9).

Inserção à cauda

Neste caso, podemos ver na figura acima, o novo nó com o valor 4220 é introduzido à cauda (fim) da lista. Para tal, é necessário acedermos ao último nó para alterar o apontador do nó seguinte de NULL para o novo nó com o valor 4220. Vejamos o aspecto do nosso código em C++:

    no = (No*) malloc(sizeof(No));
    no->valor=4220;
    no->seguinte = NULL;
    if (cabeca==NULL) {
        cabeca = no;
    }
    else {
        No *procura_ultimo = cabeca;
        while (procura_ultimo->seguinte!=NULL) {
            procura_ultimo = procura_ultimo->seguinte;
        }
        procura_ultimo->seguinte = no;
    }

Repare que, mais uma vez, na linha 4, testamos se a lista está vazia! Se estiver, a inserção é igual à inserção à cabeça de uma lista vazia (linha 5). Caso contrário, teremos que varrer toda a lista, desde a cabeça, até chegarmos ao último nó (cujo apontador para o nó seguinte é NULL – linha 9). Por fim, adicionamos o nosso novo nó no apontador “seguinte” do último nó (linha 12). Repare também que, o novo nó tem o seu apontador “seguinte” a NULL, pois este irá ser o novo último nó.

Podemos facilitar o acesso ao último elemento se tivermos um outro apontador para a cauda (como usamos nas listas duplamente ligadas). Não vou abordar este caso, mas será um bom exercício para o leitor!

Inserção a meio da lista

Imagine-se agora, que se pretende introduzir o novo nó entre o primeiro e o segundo nó. Neste caso, precisamos de ter acesso ao nó que antecede a posição onde queremos introduzir o novo nó e copiar o apontador do nó seguinte desse nó (no exemplo, o nó com o valor 1234) para o apontador do nó seguinte do novo nó. Desta forma, o nó “1234”, que apontava para o nó “790”, passa a apontar para o novo nó “4220” e este aponta agora para o “790”. Esta implementação é válida para qualquer posição (depois da cabeça), incluindo uma inserção à cauda. Repare que é de todo idêntico, pois ao copiar o nó seguinte do último para o novo nó, estamos a copiar o NULL em vez de um apontador para um possível nó seguinte.

Não vou para já demonstrar este código, pois será introduzido numa função para introduzir valores de forma ordenada, na terceira parte deste artigo. Mas como sugestão, convido o leitor a tentar escrever este código!

Na segunda parte, vamos ver como remover nós e dar um exemplo completo que insere nós à cabeça e à cauda, lista os valores dos nós e remove um nó com um dado valor.

– Listas ligadas simples em C++ (Parte II)

E na terceira parte deste artigo iremos implementar esta lista em classes.

– Listas ligadas simples em C++ (Parte III)

Este artigo foi escrito de acordo com a antiga grafia.