Listas

O que são as Estruturas de Dados do tipo Lista?

As listas representam um conjunto dinâmico cujos elementos podem ser inseridos e retirados de qualquer parte da estrutura, assim como uma lista de compras.

Fonte: Shutterstock.

Deseja ouvir este material?

Áudio disponível no material digital.

Convite ao estudo

Caro aluno, a maior parte dos sistemas de software existentes hoje em dia utiliza Estrutura de dados (ED) em seu código fonte; desde um sistema bancário até aquele seu jogo de última geração preferido, passando pelos aplicativos móveis que estão no seu smartphone. Por exemplo, ao fazer a compra de uma passagem aérea, você entra em uma lista de passageiros; ao fazer o pedido em uma lanchonete, seu pedido entra em uma fila de espera para ser preparado; por último, ao utilizar a função desfazer do seu editor de textos, você está pedindo a ele que desfaça o último comando de uma pilha de comandos realizados por você no editor. Todas as palavras destacadas anteriormente são exemplos de estruturas de dados que você aprenderá a desenvolver e usar nesta unidade. E não é apenas isso: sempre quando você utiliza um tipo de dado em uma linguagem como C, em última análise, você está utilizando uma estrutura de dados, que nada mais é do que um tipo de dado associado a um conjunto de operações que podem ser realizadas sobre ele. Enfim, já deu para perceber a importância desse conceito de estrutura de dados, certo?

Até aqui, você aprendeu a respeito das ferramentas básicas que quase todo tipo de linguagem de programação apresenta, tais como atribuições, funções, variáveis e constantes, entre outros. Como você verá, elas serão fundamentais para o que vamos aprender nesta seção.

A partir de agora, você conhecerá o conceito de listas ligadas, um tipo de ED, sua construção e uso adequados, bem como sua aplicação em programas de computador (Seção 1). Logo após, nas Seções 2 e 3, você verá como implementar outros tipos de ED que também são muito importantes, tais como pilhas e filas.

Bons estudos!

Praticar para Aprender

Você foi contratado como desenvolvedor de uma empresa do ramo de jogos digitais. Como primeira tarefa, você foi encarregado de desenvolver uma Estrutura de Dados (ED) do tipo lista para ser usada em vários jogos desenvolvidos pela empresa. Felizmente, você tinha acabado de aprender a implementar esse tipo de ED na faculdade. Então você fez um ótimo trabalho, implementando as funções básicas da lista, e sua estrutura de dados está sendo usada em vários jogos na empresa, o que deixou seu chefe muito contente.

Contudo, novas demandas surgiram e você deve implementar novas funções para sua ED, visando atender às necessidades da empresa. Seu chefe confiou a você a implementação das seguintes funções:

• posicao_menor(li): retorna a posição menor elemento da lista “li”; e
• existe(li, item): verifica se o “item” existe ou não na lista “li”.

Para demonstrar seu trabalho, ele pediu que você usasse a função “posicao_menor”, desenvolvida por você para apresentar o nome do inimigo que está mais próximo do jogador em determinado momento do jogo. O prazo para resolver esse desafio não é tão longo, então, bom trabalho!

conceito-chave

Conjuntos são fundamentais para a computação, assim como o são para a matemática. Enquanto os conjuntos matemáticos são invariáveis, os conjuntos manipulados por algoritmos podem crescer, diminuir ou sofrer mudanças em seus elementos ao longo da execução de um programa (CORMEN et al., 2012).

Os conjuntos que apresentam tais características são conhecidos como conjuntos dinâmicos e são indispensáveis para se resolver uma série de problemas em computação. Algoritmos podem exigir a execução de vários tipos de operações em conjuntos, como testar a pertinência de um elemento no conjunto, inserir ou eliminar um determinado elemento e outros.

Um mecanismo utilizado para organizar nossa informação e prover operações convenientes e eficientes para acessá-la e manipulá-la é conhecido como estrutura de dados.

Diversos tipos de estruturas de dados têm sido propostos e o conhecimento das características dessas estruturas é um fator importante para a escolha da estrutura que melhor se encaixa na solução de um determinado problema. Nesta unidade, examinaremos a representação de conjuntos dinâmicos por meio de três estruturas de dados elementares amplamente conhecidas como lista, pilha e fila.

Vamos começar, então, com as listas.

Lista

A lista representa um conjunto dinâmico cujos elementos podem ser inseridos e retirados de qualquer parte da estrutura. Trata-se da estrutura mais flexível, em termos de liberdade para a manipulação de elementos, se comparada com as outras estruturas que apresentaremos.

A analogia que pode ser feita para esta estrutura de dados é uma lista de compras de um supermercado. Uma lista de compras pode ser consultada em qualquer ordem e os itens dessa lista podem ser encontrados à medida que a pessoa caminha pelo supermercado; assim, um item no meio da lista pode ser removido antes do item do início da lista.

Devido à sua flexibilidade, a lista é uma das estruturas mais utilizadas para o desenvolvimento de softwares, em geral. As principais operações que devem estar presentes em uma ED do tipo lista são:

• criar(): cria e retorna uma lista vazia.
• inserir(li, pos, item): adiciona o elemento “item” na posição “pos” da lista “li”.
• remover(li, pos): remove e retorna o elemento da posição “pos” da lista “li”.
• obter(li, pos): retorna (sem remover) o elemento da posição “pos” da lista “li”.
• tamanho(li): retorna a quantidade de elementos existentes na lista “li”.
• vazia(li): retorna se a lista “li” está vazia ou não.
• liberar(li): desaloca a lista “li” da memória do computador.

O Quadro 4.1 apresenta uma série de operações e seus efeitos sobre uma ED lista. Considere que o elemento mais à esquerda da lista consiste em seu início, cujo índice é igual a 0 (zero) e o elemento mais à direita, o seu fim, cujo índice é igual ao tamanho da lista menos um.

Lista simplesmente ligada

Podemos implementar ED na linguagem C de pelo menos duas formas: utilizando vetores ou utilizando estruturas ligadas (ou encadeadas). Estruturas de dados ligadas alocam espaços na memória do computador à medida que novos elementos precisam ser adicionados e os desalocam à medida que não precisamos mais deles. Por isso, é dito que as estruturas de dados ligadas proporcionam uma melhor utilização da memória.

Observe a ilustração de uma lista simplesmente ligada na Figura 4.1.

Uma lista simplesmente ligada consiste em uma sequência de elementos, denominados nós (representados por retângulos com uma seta em uma de suas extremidades na Figura 4.1). Cada nó possui uma informação (valor que aparece dentro do retângulo) e um ponteiro para o próximo nó da lista (seta na extremidade direita do retângulo). O último nó da lista aponta para NULL, representando que não existe um próximo nó na lista. A lista propriamente dita é representada apenas por um ponteiro para o primeiro nó dessa lista, chamado de Início na Figura 4.1.

Uma lista simplesmente ligada tem esse nome porque cada nó da estrutura tem apenas um ponteiro para o próximo nó da lista. Existe também o conceito de lista duplamente ligada, que veremos mais à frente nesta seção. Em uma lista duplamente ligada, cada nó apresenta dois ponteiros, um que aponta para o próximo nó e outro que aponta para o nó anterior.

Vamos, neste momento, passar à parte prática e implementar nossa primeira ED, uma lista simplesmente ligada.

Começaremos criando algumas structs. O conceito já foi apresentado, mas, para relembrar, structs permitem ao programador criar variáveis compostas heterogêneas na linguagem C. Com structs você consegue criar variáveis que podem armazenar mais de uma informação, assim como os vetores. Mas, ao contrário dos vetores, que só permitem armazenar valores de um mesmo tipo, structs oferecem a possibilidade de armazenarmos valores de tipos diferentes, tais como números e caracteres, entre outros (por isso são chamadas de variáveis compostas heterogêneas). 

Na linguagem C, a criação de uma estrutura deve ser feita fora de qualquer função e deve apresentar a seguinte sintaxe:

struct <nome>{
  <tipo> <nome_da_variavel1>;
  <tipo> <nome_da_variavel2>;
  ...
};

<nome> é o nome da estrutura, por exemplo, cliente, carro, fornecedor, nó, lista e outros. As variáveis internas são os campos da struct, nos quais se deseja guardar as informações.

Agora que revisamos rapidamente o conceito de struct, vamos criar uma struct para representar cada nó da nossa lista simplesmente ligada.

Como vimos anteriormente, cada nó contém uma informação e um ponteiro para o próximo nó. Assim, a struct para o nó de lista ficará assim:

struct No {
  int info;
  struct No* proximo;
};

Por questão de simplicidade, estamos considerando que a informação presente em um nó (definida pela variável “info”) é um número inteiro. Contudo, você pode armazenar qualquer tipo de informação que desejar, como strings, número reais, ou até mesmo uma variável de outro tipo struct.

É possível ver que o campo “proximo” é um ponteiro que aponta para outro nó da estrutura. Para declarar um ponteiro, utilizamos o operador * após o tipo da variável.

Uma vez criada a struct que representa um nó da lista, precisamos de uma struct para representar a lista propriamente dita. Essa struct deve conter, como campos, um ponteiro para o primeiro nó da lista e a quantidade de elementos presentes nessa lista. O código dessa struct é o seguinte:

struct Lista {
  struct No* inicio;
  int tamanho;
};

Partiremos agora para a implementação do comportamento que “dará vida” a nossa ED, isto é, as funções que nos permitirão criar uma lista, inserir, remover e consultar elementos nela, entre outras coisas.

A primeira e uma das mais importantes funções que vamos implementar é a função que cria a própria lista. Vejamos o código desta função (Código 4.1) e, depois, a explicaremos passo a passo.

struct Lista* criar() {
    struct Lista* nova_lista = (struct Lista*) malloc(sizeof(struct Lista));
    if (nova_lista != NULL) {
        nova_lista->inicio = NULL;
        nova_lista->tamanho = 0;
    }
    return nova_lista;
}

Basicamente, o que essa função faz é instanciar dinamicamente uma variável do tipo struct “Lista” na memória (linha 2) e configurar os valores de seus campos. O campo “inicio”, que é um ponteiro, deve apontar para NULL, uma vez que estamos criando uma lista vazia (linha 4). NULL é uma palavra reservada da linguagem C, muito usada com ponteiros, indicando que ele não está apontando para qualquer posição de memória válida do computador. Analogamente, o campo “tamanho” deve ser inicializado com o valor igual a 0 (zero) – linha 5. Feito isso, deve-se retornar o endereço da memória alocado para a variável do tipo “Lista” (linha 7). Um ponto importante a destacar é que, antes de configurar os valores dos campos da struct “Lista”, é preciso testar se a memória foi corretamente alocada para a lista (linha 3). Isso é importante, pois caso a função “malloc” não consiga alocar o espaço necessário para a lista, ela retornará o valor NULL.

Ao utilizar a função “malloc” quando criamos um ponteiro para uma variável do tipo de struct, a forma de acesso aos campos da struct muda. Em vez de usarmos o operador. (ponto), passamos a utilizar o operador  (seta), conforme pode ser visto nas linhas 4 e 5 no Código 4.1.

Já podemos criar e utilizar nossa primeira lista simplesmente ligada. Mas, antes disso, vamos implementar mais uma função, a saber, a função que verifica se a lista está vazia ou não. Para sabermos se uma lista está vazia ou não, basta verificar se o ponteiro “inicio” da lista está apontando para NULL. Para isso, é preciso ter acesso à lista, que será passada por referência para a função. Veja, no Código 4.2, o código da função que verifica se a lista está vazia.

#include <stdbool.h>
#include <assert.h>
bool vazia(struct Lista* li) {
    assert(li != NULL);     
    if (li->inicio == NULL) {
        return true;
    } else {
        return false;
    }
} 

Dois destaques para essa função são necessários. Primeiramente, estamos utilizando o tipo de dados bool, que não existe, por padrão, na linguagem C. Então, para utilizá-lo, é preciso importar a biblioteca <stdbool.h>, como pode ser visto no Código 4.2 (linha 1). Outro ponto importante é o uso da instrução “assert()” (linha 4). Essa instrução é implementada pela biblioteca <assert.h> (linha 2) e seu objetivo é verificar o resultado de uma expressão lógica passada por parâmetro para ela. Caso o resultado da expressão seja verdadeiro, o fluxo do programa segue normalmente, caso contrário, o programa é abortado (terminado) e um erro é apresentado ao usuário. Isso é necessário porque, antes de realizar qualquer operação sobre a lista, é importante verificar se o endereço de memória apontado por ela não é NULL.

Agora podemos usar nossa lista. Vamos criar uma lista vazia e testar se ela realmente está vazia. Para isso, utilizamos a função main(), como pode ser visto no Código 4.3.

int main() {
   struct Lista* minha_lista = criar();
   if (vazia(minha_lista) == true) {
       printf("\nOK, lista vazia!");
   } else {
       printf("\nOps... algo deu errado!");
   } 
   return 0;
}

Na linha 2 criamos uma lista vazia, usando a função “criar()”, e armazenamos o endereço dessa lista no ponteiro “minha_lista”. Nós usaremos esse ponteiro sempre que quisermos realizar alguma operação em nossa lista. Logo após, nas linhas 3 a 7, estamos testando se a lista está vazia, por meio da função “vazia()”, e imprimindo uma mensagem apropriada na tela. Visualmente falando, o resultado da execução do código apresentado no Código 4.3 é o que pode ser visto na Figura 4.2.

 O código completo da nossa ED lista simplesmente ligada até o momento pode ser visto a seguir, utilizando a ferramenta Paiza.io.

Trataremos, agora, de algumas funções mais desafiadoras. Vamos pensar na função que insere um novo elemento na lista. Como dissemos anteriormente, a ED lista é a estrutura mais flexível de todas que estudaremos nesta unidade, permitindo a inserção de elementos em quaisquer posições da lista.

Vamos iniciar com a implementação da função inserir, conforme pode ser visto no Código 4.4.

void inserir (struct Lista* li, int pos, int item) {
    assert(li != NULL);
    assert(pos >= 0 && pos <= li->tamanho);
    struct No* novo_no = (struct No*) malloc(sizeof(struct No));
    novo_no->info = item;
    if (pos == 0) {
        novo_no->proximo = li->inicio;
        li->inicio = novo_no; 
    } else {
       struct No* aux = li->inicio;
       for(int i = 0; i < pos - 1; i++) {
           aux = aux->proximo;
       }
       novo_no->proximo = aux->proximo;
       aux->proximo = novo_no;
    }
    li->tamanho++; 
}

O primeiro passo dessa função é verificar se o ponteiro que representa a lista, “li”, não é nulo (linha 2). Logo após, precisamos verificar se a posição em que o elemento será inserido é válida (linha 3). No caso da função “inserir”, podemos passar como posição qualquer número entre 0 e n, onde n corresponde à quantidade de elementos da lista.

Feito isso, precisamos instanciar um novo nó, que armazenará o novo elemento a ser inserido na lista (linha 4). Feito isso, devemos atualizar a variável “info” do novo nó com a informação recebida no parâmetro “item” da função (linha 5). Antes de continuar, precisamos fazemos um teste para verificar se se trata de uma inserção no início da lista ou não. Mas por que isso? Porque, como veremos, o processo de inserção de um elemento no início da lista é diferente do processo de inserção nas demais posições da lista.

Caso a inserção seja no início da lista, isto é, o valor do parâmetro “pos” seja igual a 0 (zero), devemos fazer com que o ponteiro “próximo” desse nó aponte para o endereço que está sendo apontado pelo ponteiro “inicio” da lista (linha 7). Isso ocorre porque, como estamos inserindo um nó no início da lista, o novo nó passará a ser o primeiro elemento da lista e o nó que era o primeiro, passará a ser o segundo. Contudo, se paramos aqui, teremos um problema, pois o ponteiro “inicio” da lista continuará apontando para o mesmo lugar. Devemos, então, atualizá-lo para que ele aponte para o novo nó (linha 8).

Se a inserção era para ser realizada no início da lista, o procedimento está completo. É importante incrementarmos o valor da variável “tamanho” da lista (linha 17), uma vez que um novo elemento foi inserido nela.

E se quisermos inserir um elemento em qualquer outra posição da lista, entre o início (definido pela posição 0) e o fim (definido pela posição n, onde n corresponde ao tamanho da lista)? A função “inserir” trata esse caso no seu bloco “else”, localizado entre as linhas 9 e 16.

Mas por que há um tratamento diferente para os casos de inserção em outras posições da lista? A resposta é que, ao contrário do que acontece com o primeiro elemento da lista, nós não temos acesso direto a cada nó da lista. Assim, precisaremos percorrer essa lista até encontrar a posição em que gostaríamos de adicionar um novo elemento. Isso é feito nas linhas 10 a 13 do código da função “inserir”. Inicialmente é criado um ponteiro auxiliar, denominado “aux” (você pode dar o nome que quiser para ele) e fazê-lo apontar para o primeiro elemento da lista (linha 10). Logo depois, utilizamos uma estrutura de repetição for para percorrer a lista, atualizando o valor do ponteiro “aux” a cada iteração.

Supondo que desejamos inserir um novo elemento na posição 3 da lista apresentada na Figura 4.3, o ponteiro “aux” deve estar posicionado exatamente sobre o elemento 6, quando o trecho de código das linhas 10 a 13 for executado.

Conforme pode ser percebido, o ponteiro “aux” apontará para o nó anterior à posição em que o novo elemento será inserido. E para que? Isso é importante porque precisamos atualizar o ponteiro próximo do novo nó, fazendo-o apontar para o próximo do nó “aux” (linha 14), bem como atualizar o ponteiro “proximo” do nó “aux”, fazendo-o apontar para o nosso novo nó. O resultado visual dessa inserção pode ser visto na Figura 4.4.

Até o momento, criamos funções que nos permitem inserir elementos em uma lista simplesmente ligada. Antes de passarmos para as demais funções da lista, vamos criar uma função que, por padrão, não existe nesta ED, mas que será útil para verificar o correto funcionamento da lista. Trata-se da função “imprimir”, que será responsável por imprimir todos os elementos da lista, do primeiro até o último. Vejamos como fica essa função no Código 4.5.

void imprimir(struct Lista* li) {
    assert(li != NULL);
    printf("\nLista: ");
    struct No* aux = li->inicio;
    for(int i = 0; i < li->tamanho; i++) {
        printf("%d ", aux->info);
        aux = aux->proximo;
    }
 }

Veja que o código é bem parecido com o da função “inserir”, com a diferença que estamos percorrendo a lista apenas para imprimir, não para inserir qualquer elemento nela.

Com isso em mãos, tente reproduzir, no papel, a execução do código da função “main()” no Código 4.6. Depois, use a função “imprimir” para confirmar sua resposta.

int main() {
     struct Lista* minha_lista = criar(); 
     inserir(minha_lista, 0, 5);      
     inserir(minha_lista, 0, 3);      
     inserir(minha_lista, 2, 6);         
     inserir(minha_lista, 1, 0);
     inserir(minha_lista, 4, 7);
     inserir(minha_lista, 1, 2);
     inserir(minha_lista, 5, 6);
     inserir(minha_lista, 3, 4);
     return 0;
}

 O código completo juntamente com a resposta pode ser visto a seguir, utilizando a ferramenta Paiza.io.

Falta-nos, agora, implementar as seguintes funções: “tamanho”, que retorna a quantidade de elementos da lista, “obter”, que retorna o elemento de determinada posição da lista, “remover”, que remove e retorna o elemento de determina posição da lista e “liberar”, que desaloca a memória usada pela lista. Dessas, a mais simples de todas é a função “tamanho”, cujo código é apresentado no Código 4.7.

int tamanho(struct Lista* li) {
   assert(li != NULL);
   return li->tamanho;
}

Essa função simplesmente acessa e retorna o valor da variável “tamanho”, armazenada na struct “Lista”. Você pode testar a função com o código do Código 4.8, cujo resultado esperado é 2.

int main() {
   struct Lista* minha_lista = criar(); 
   inserir(minha_lista, 0, 5);      
   inserir(minha_lista, 0, 3);      
   printf("\n%d", tamanho(minha_lista));
   return 0;
}

 O código completo juntamente com a resposta pode ser visto a seguir, utilizando a ferramenta Paiza.io.

A próxima função que vamos implementar é a função “obter”, cujo código fonte encontra-se no Código 4.9.

int obter(struct Lista* li, int pos) {
   assert(li != NULL);
   assert(pos >= 0 && pos < li->tamanho);
   struct No* aux = li->inicio;
   for(int i = 0; i < pos; i++) {
      aux = aux->proximo;
   }
   return aux->info; 
}

Essa função tem instruções similares às da função “inserir”, certo? Por exemplo, inicialmente, devemos verificar se a posição informada é válida, antes de retornar o elemento da lista (linha 3). A diferença, aqui, é que as posições válidas são de 0 à n – 1, onde n é o tamanho da lista. Ou seja, nós podemos inserir um novo elemento na posição n, que é a última posição da lista, mas não podemos obter um elemento da posição n, pois essa posição está “vazia”. Analogamente, nós precisamos utilizar uma estrutura de repetição for (linhas 5 a 7) para acessar a posição desejada e só depois retornar o valor do elemento (linha 8).

Vamos, agora, implementar a função “remover” (Código 4.10). Faremos da mesma forma que fizemos com a função “inserir”, apresentando inicialmente o código e comentando-o passo a passo.

int remover(struct Lista* li, int pos) {
   assert(vazia(li) == false);
   assert(pos >= 0 && pos < li->tamanho);

   struct No* ant = NULL;
   struct No* aux = li->inicio;
   for(int i = 0; i < pos; i++) {
      ant = aux;
      aux = aux->proximo;
   }

   if (ant == NULL) {
       li->inicio = aux->proximo;
   } else {
       ant->proximo = aux->proximo;
   }

   int elemento = aux->info;
   li->tamanho--;
   free(aux);
   return elemento;
}

A função “remover” inicia verificando se a lista não está vazia (linha 2). Isso é importante, porque é impossível remover qualquer elemento de uma lista vazia. Posteriormente, verifica-se se a posição a ser removida é válida (linha 3). Assim, como na função “obter”, nós só podemos remover elementos que estão entre as posições 0 e n – 1, onde n é o tamanho da lista. 

Atenção: diferentemente do que fizemos na função “inserir”, para a função “remover” precisamos de dois ponteiros auxiliares, denominados “ant” e “aux” (linhas 5 e 6). O ponteiro “ant” apontará para o nó anterior à posição que desejamos remover. Isso é necessário, pois precisaremos atualizar o ponteiro “proximo” desse nó, uma vez que o nó a sua frente será removido. O ponteiro “aux” apontará exatamente para o nó que desejamos remover. É por meio dele que teremos a referência para a posição de memória a ser liberada.

O laço for (linhas 7 a 10) percorre a lista até encontrar o nó da posição que desejamos remover. Veja como ficariam os ponteiros “ant” e “aux” caso desejássemos remover o nó da posição 3 da lista da Figura 4.5.

As linhas 12 a 16 atualizam alguns ponteiros, antes de realizar a remoção do nó apontado por “aux”. Quando o nó “ant” aponta para NULL, significa que estamos tentando remover o elemento da primeira posição. Assim, temos que atualizar o ponteiro “inicio” da lista para que ele aponte para o segundo elemento da lista (linha 13). Caso o ponteiro “ant” não aponte para NULL, então queremos remover algum nó que esteja entre o segundo e último nó da lista. Nesse caso, devemos atualizar o ponteiro “proximo” do nó apontado por “ant”.

Em seguida, na linha 18, armazenamos a informação do nó em uma variável, denominada “elemento”. Isso é importante, pois precisaremos retornar o valor armazenado no nó ao final da execução da função. A linha 19 simplesmente decrementa o valor da variável “tamanho” da lista. Após isso, é necessário desalocar a memória alocada para nó da lista, usando a função “free” (linha 20).

Todas as vezes em que alocamos memória com a função “malloc” devemos usar a função “free” para desalocá-la. Caso contrário, a memória continuará reservada para o programa até o final de sua execução. Por fim, na linha 21, retornamos à informação armazenada no nó que foi removido.

Agora só precisamos implementar a função “liberar” e teremos a nossa lista simplesmente encadeada completa e funcional. A função liberar é bem simples, pois ela utiliza duas funções já implementadas anteriormente. Essa é uma das grandes vantagens do uso de funções: a reutilização de código. Observe o código da função liberar no Código 4.11.

void liberar(struct Lista* li) {
   while(vazia(li) == false) {
      remover(li, 0);
   }
   free(li);
}

Nessa função não precisamos usar a instrução “assert”, pois a função “vazia” já faz essa verificação por nós. O funcionamento da função “liberar” consiste em remover elementos do início da lista enquanto a lista não estiver vazia (linhas 2 a 4). Por fim, a memória alocada para a struct “Lista” também é liberada na linha 5, por meio da função “free”.

 O código completo da ED lista simplesmente encadeada pode ser visto a seguir, utilizando a ferramenta Paiza.io.

Lista duplamente ligada

Uma limitação da ED lista simplesmente ligada é que qualquer inserção/remoção/leitura feita no final da lista tem um custo computacional alto, pois é preciso percorrer todos os nós da lista até encontrar a última posição. Esse custo é ainda maior se quisermos, por exemplo, percorrer a lista de trás para frente, ou seja, do último elemento para o primeiro.

Para tentar mitigar essas limitações, surgiu o conceito de lista duplamente ligada. Há duas diferenças importantes da lista duplamente ligada para a lista simplesmente ligada.

1. Cada nó possui, além do ponteiro para o próximo nó, um ponteiro para o nó anterior. Isso permite que consigamos navegar na lista de trás para frente.
2. A lista apresenta, além do ponteiro para o primeiro nó, um ponteiro para o último nó da lista. Isso permite que consigamos ler, inserir e remover elementos no final da lista, sem precisar percorrê-la toda.

Veja as alterações necessárias no código das structs “Lista” e “No” de uma lista duplamente ligada:

struct No {
  int info;
  struct No* anterior;
  struct No* proximo;
};

struct ListaDupla {
  struct No* inicio;
  struct No* fim;
  int tamanho;
};

Para diferenciarmos da lista simplesmente ligada, nós mudamos o nome da struct “Lista” para “ListaDupla”.

A ilustração de uma lista duplamente ligada pode ser visualizada na Figura 4.6. A seta apontada para a esquerda representa o ponteiro “anterior” de um nó.

A partir de agora, apresentaremos as mesmas operações da lista simplesmente ligada, comentando a diferença de implementação para o caso da lista duplamente ligada.

Comecemos pela função “criar” (Código 4.12).

struct ListaDupla* criar() {
    struct ListaDupla* nova_lista = (struct ListaDupla*) malloc(sizeof(struct ListaDupla));
    if (nova_lista != NULL) {
        nova_lista->inicio = NULL;
        nova_lista->fim = NULL;
        nova_lista->tamanho = 0;
    }
    return nova_lista;
}

A única diferença, para esta função, é que agora temos que inicializar também o ponteiro “fim” da struct “ListaDupla” com o valor NULL, pois a lista é criada vazia.

O código da função “vazia” se mantém praticamente o mesmo, a não ser pelo nome da struct que mudou para “ListaDupla” (Código 4.13). Isso porque a forma de verificar se uma lista está vazia é a mesma, tanto para a lista simplesmente ligada quanto para a duplamente ligada.

bool vazia(struct ListaDupla* li) {
    assert(li != NULL);     
    if (li->inicio == NULL) {
        return true;
    } else {
        return false;
    }
}

O mesmo ocorre com as funções “tamanho” e “liberar”. Assim, o código dessas funções não será apresentado aqui novamente.

Vamos, então, olhar para aquelas funções que sofreram maiores modificações, a saber, as funções “inserir” e “remover”. Isso porque agora nós temos que atualizar também os ponteiros “anterior”, da struct “No”, e “fim”, da struct “ListaDupla”.

Vamos começar pela função “inserir”, cujo código encontra-se no Código 4.14.

void inserir (struct ListaDupla* li, int pos, int item) {
    assert(li != NULL);
    assert(pos >= 0 && pos <= li->tamanho);

    struct No* novo_no = (struct No*) malloc(sizeof(struct No));
    novo_no->info = item;
    if (pos == 0) {
        novo_no->anterior = NULL;
        novo_no->proximo = li->inicio;
        li->inicio = novo_no; 
        if (li->fim == NULL) {
            li->fim = novo_no;
        } 
    } else if (pos == li->tamanho) { 
        novo_no->anterior = li->fim;
        novo_no->proximo = NULL;
	 li->fim->proximo = novo_no;
        li->fim = novo_no;    
    } else {
       struct No* aux = li->inicio;
       for(int i = 0; i < pos - 1; i++) {
           aux = aux->proximo;
       }
       novo_no->anterior = aux;
       novo_no->proximo = aux->proximo;
       aux->proximo = novo_no;
    }
    li->tamanho++; 
}

No trecho de código das linhas 8 a 13, que trata da inserção do início da lista, foi preciso incluir instruções para atualizar o ponteiro “anterior” do novo nó para NULL, pois não há nós anteriores ao nó inicial. Também foi preciso atualizar o ponteiro “fim” da lista, no caso de ser a inserção do primeiro elemento da lista, ou seja, quando a lista tem apenas um elemento, tanto o ponteiro “inicio” quanto o “fim” apontam para o mesmo elemento.

O bloco else-if das linhas 14 a 18 é inédito e trata da inserção no final da lista. Agora, como temos acesso direto ao último elemento da lista, não precisaremos mais percorrê-la até o fim. Basta atualizarmos o ponteiro “fim” da lista. Essa é a grande vantagem da lista duplamente ligada: a inserção de um elemento tanto no início da lista quanto no seu fim tem um desempenho muito bom.

Por fim, o trecho de código das linhas 19 a 27, que trata da inserção de um elemento em qualquer posição entre o primeiro e o último elemento, é bem similar ao da lista simplesmente ligada, com a exceção que, agora, é preciso atualizar o ponteiro “anterior” do nó que está sendo inserido.

Passando agora para a função “remover”, o código para a lista duplamente ligada está no Código 4.15.

int remover(struct ListaDupla* li, int pos) {
   assert(vazia(li) == false);
   assert(pos >= 0 && pos < li->tamanho);
   struct No* aux = NULL;

   if (pos == 0) {
       aux = li->inicio; 
       li->inicio = aux->proximo;
       if (li->inicio == NULL) {
           li->fim = NULL;
       } else {
           li->inicio->anterior = NULL;        
       }
   } else if (pos == li->tamanho - 1) {
       aux = li->fim;
       li->fim = aux->anterior;
       li->fim->proximo = NULL;        
   } else {
       struct No* ant = NULL;
       aux = li->inicio;
   
       for(int i = 0; i < pos; i++) {
            ant = aux;
            aux = aux->proximo;
       }

       ant->proximo = aux->proximo;
       aux->proximo->anterior = ant;    
    }

   int elemento = aux->info;
   li->tamanho--;
   free(aux);
   return elemento;
}

De forma análoga ao que fizemos na função “inserir”, também precisamos verificar se se trata de uma remoção no início da lista, no fim ou em qualquer outra posição entre o início e o fim. Isso é feito por meio do comando if-else-if, contido no código. Caso seja uma remoção no início da lista, além do que já fizemos para a lista simplesmente ligada, devemos atualizar o ponteiro “anterior” do nó que estava na segunda posição da lista, bem como do ponteiro “fim”, da lista (caso a lista tenha ficado vazia) – linhas 8 a 13. Também criamos uma sequência de instruções para o caso de a remoção ocorrer no final da lista (linhas 15 a 17). Nesse caso, devemos atualizar o ponteiro “fim” da lista (linha 16), bem como o ponteiro “próximo” do penúltimo nó da lista, fazendo-o apontar para NULL, pois ele passará a ser o último nó da lista (linha 17). Por último, das linhas 19 a 28, temos o caso de remoção para qualquer elemento entre o primeiro e o último elemento. As diferenças para a função remover da lista simplesmente ligada são que, agora, precisamos atualizar o ponteiro “anterior” do elemento subsequente ao que será sendo removido (linha 28). A sequência de comandos responsável por liberar espaço da memória e retornar a informação contida no elemento removido (linhas 31 a 34) mantém-se a mesma da função da lista simplesmente ligada.

Para terminar, vejamos o código da função “obter” para a lista duplamente ligada (Código 4.16).

int obter(struct ListaDupla* li, int pos) {
   assert(li != NULL);
   assert(pos >= 0 && pos < li->tamanho);
   struct No* aux;

   if (pos == 0) {
      aux = li->inicio;
   } else if (pos == li->tamanho - 1) {
      aux = li->fim;
   } else {
      aux = li->inicio;
      for(int i = 0; i < pos; i++) {
         aux = aux->proximo;
      }
   }
   return aux->info; 
}

A diferença dessa função é que, agora, temos condições de acessar a última posição da lista sem ter que percorrê-la, como era feito na lista simplesmente ligada. Isso é feito acessando diretamente o ponteiro “fim” na lista, como mostra a linha 9.

 Chegamos ao final desta seção. Você pode encontrar o código completo da lista duplamente ligada a seguir, utilizando a ferramenta Paiza.io.

Para aprimorar seus conhecimentos, não deixe de resolver os exercícios do final da seção, assim como a situação-problema apresentada a seguir.

Bons estudos!

Faça valer a pena

void inserir_inicio(struct Lista* li, int item) {
   assert(li != NULL);
   struct No* novo_no = (struct No*) malloc(sizeof(struct No));
   novo_no->info = item;
   _________________________;
   _________________________; 
   li->tamanho++; 
}

Referências

CORMEN, T. H. et al. Algoritmos: teoria e prática. Elsevier, 2012.

LINKED List Animation. [S. l.], 14 ago. 2017. (3 min. 11 seg.). Publicado pelo canal Technology Premiere. Disponível em: https://bit.ly/36juGFo. Acesso em: 16 jan. 2021.

THE HUXLEY. Página inicial. The Huxley, [s. d.]. Disponível em: https://www.thehuxley.com. Acesso em: 12 jan. 2021.

THE HUXLEY. Unindo listas. The Huxley, 2018. Disponível em: https://bit.ly/3agGIAw. Acesso em: 16 jan. 2021.