O objetivo dessa unidade é apresentar o conteúdo relacionado a Listas. Será feita uma abordagem focando na linguagem C.
Até agora temos trabalhado com estruturas de dados, das mais simples às mais complexas, que têm tamanho fixo. Por esta razão, denominam-se estruturas de dados estáticas (o seu tamanho e localização na memória não se alteram durante a execução).
Pois bem, agora vamos unir as estruturas estáticas juntamente com a alocação dinâmica e usar esses poderosos conceitos para criar outro importante, o de estruturas de dados dinâmicas, ou seja, as estruturas de dados que são alocadas, realocadas e movidas o quanto e do jeito que quisermos.
A partir daí, poderemos trabalhar com conjuntos de dados dinâmicos, com por exemplo uma coleção de números, dados de um funcionário, dados de um produto, entre outros. O que difere esses dados dos demais é a necessidade de manipulações que faça com que eles possam crescer, encolher, sofrer alterações ao logo da execução de determinado programa.
A primeira estrutura dinâmica que iremos estudar são as listas.
Uma lista encadeada é uma estrutura de dados que representa um conjunto de dados organizados em ordem linear e dinâmica. Ela é composta por células também chamadas de nós (aqui adotaremos essa nomenclatura), que utilizando um ponteiro apontam para o próximo elemento da lista, e seu último elemento aponta para NULL, sinalizando que não existe um próximo elemento. Para que uma lista encadeada exista, basta guardar seu primeiro elemento. O primeiro é ligado no segundo, que é ligado no terceiro etc.
Numa lista encadeada, para cada novo elemento inserido na estrutura, alocamos um espaço de memória para armazená-lo. Desta forma, o espaço total de memória gasto pela estrutura é proporcional ao número de elementos nela armazenado. No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo, portanto não temos acesso direto aos elementos da lista. Para que seja possível percorrer todos os elementos da lista, devemos explicitamente guardar o encadeamento dos elementos, o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro para o próximo elemento da lista
Para representarmos um elemento da lista simplesmente encadeada (um nó) vamos utilizar uma struct, que chamaremos de No. Vejamos:
struct No{ int num; struct No *prox; }; typedef struct No No;
Cada nó de uma lista simplesmente encadeada irá possuir pelo menos (pode ser mais de um) um atributo que corresponde a determinado dado a ser armazenado pela lista (int, float, char, struct..) e um ponteiro (do tipo No) que será utilizado para armazenar o endereço de memória do próximo nó (dessa maneira "ligamos" um nó a outro nó). Aqui utilizaremos uma lista para armazenar inteiros (int num) e o ponteiro do tipo No que apontará para o próximo nó sera *prox.
Para o controle da lista utilizaremos uma estrutura do tipo Lista. Ela contém dois ponteiros do tipo No (inicio e fim), que irão armazenar os endereço de memória do primeiro e do último elemento da lista respectivamente.
/*registro do tipo Lista contento dois ponteiros do tipo nó para controlar a lista*/ struct Lista{ struct No *inicio; /*aponta para o elemento do início da lista*/ struct No *fim; /*aponta para o elemento do fim da lista*/ }; typedef struct Lista Lista;
Para auxiliar em algumas funções, é necessário utilizar dois ponteiros auxiliares do tipo No. Então definimos abaixo:
/*necessitaremos também de dois ponteiros auxilares *aux e *anterior */
No *aux;
No *anterior;
Nesse ponto definiremos também uma função cria_lista( ). Ela será utilizada para criar uma lista, ou seja, alocará dinamicamente o espaço necessário para armazenar seus ponteiros (inicio e fim ) e irá inicializá-los com NULL. Isso indica que a lista inicialmente está vazia.
Lista* cria_lista(){
/*alocação do ponteiro li para controlar a lista*/
Lista* li = (Lista*) malloc(sizeof(Lista));
if(li != NULL){
/*Se a lista está inicialmente vazia, inicio e fim apontam para NULL */
li->fim = NULL;
li->inicio = NULL;
}
return li;
}
Na função main, devemos definir um ponteiro do tipo Lista. Ele irá receber o endereço do espaço alocado pela função cria_lista( ) e também servirá de parâmetro para as demais funções seguintes.
int main(){ Lista *li = cria_lista(); ...blocos de chamada de função... return 0; }
Como o próprio nome descreve é uma lista simplesmente encadeada em que não há qualquer tipo de ordenação em relação aos nós pertencentes à lista. A disposição dos mesmos dependerá da ordem e local (início ou fim da lista) em que forem inseridos.
Para este tipo de lista realizaremos 5 operações:
Esta é a implementação da função que utilizaremos para inserir um dado no início da lista.
void insere_inicio_lista(Lista *li){ /*a cada inserção alocamos dinamicamente um espaço para um novo nó*/ No *novo =(No*) malloc(sizeof(No)); /*o número a ser inserido será armazenado em novo->num*/ printf("Digite o numero a ser inserido no inicio da lista: "); scanf("%d",&novo->num); /*caso a lista estiver vazia o primeiro elemento a ser inserido será o primeiro e último*/ if(li->inicio == NULL){ /*aqui fazemos com que inicio aponte para o mesmo endereço que novo aponta*/ li->inicio = novo; novo->prox = NULL; /*aqui fazemos com que fim aponte para o mesmo endereço que novo aponta*/ li->fim = novo; /*caso a lista não esteja vazia*/ }else{ /*como a inserção é no inicio, o novo nó inserido receberá no atributo prox o endereço que inicio aponta, ou seja, o inicio anterior será agora o segundo elemento, portante o primeiro elemento da lista terá que apontar para ele*/ novo->prox = li->inicio; /*aqui fazemos com que inicio aponte para o mesmo endereço do novo nó inserido*/ li->inicio = novo; } printf("\nNumero inserido no inicio da lista!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos os ponteiros inicio e fim apontados para null:
Agora inseriremos o número 3 no início da lista.
Depois vamos inserir o número 9 no início da lista.
Agora trataremos de inserir dados no fim da lista. Vejamos a implementação:
void insere_fim_lista(Lista *li){ /*a cada inserção alocamos dinamicamente um espaço para um novo nó*/ No *novo =(No*) malloc(sizeof(No)); /*o número a ser inserido será armazenado em novo->num*/ printf("Digite o numero a ser inserido no fim da lista: "); scanf("%d",&novo->num); /*caso a lista estiver vazia o primeiro elemento a ser inserido será o primeiro e último*/ if(li->inicio == NULL){ /*aqui fazemos com que inicio aponte para o mesmo endereço que novo aponta*/ li->inicio = novo; novo->prox = NULL; /*aqui fazemos com que fim aponte para o mesmo endereço que novo aponta*/ li->fim = novo; /*caso a lista não esteja vazia*/ }else{ /*como a inserção é no fim, o nó para o qual fim aponta, no atributo prox, receberá o endereço de novo, ou seja, o último elemento será agora o penúltimo, e portanto deverá apontar para o último elemento inseirido*/ li->fim->prox = novo; /*aqui fazemos com que fim aponte para o mesmo do novo nó inserido*/ li->fim = novo; /*aqui fazemos com que o endereço para o qual fim aponta, no atributo prox receba NULL*/ li->fim->prox = NULL; } printf("\nNumero inserido no fim da lista!"); getch(); }
Complementando a lista iniciada anteriormente, vamos inserir o número 6 no final da lista:
Por fim, vamos inserir o número 2 no final da lista:
Para imprimir os elementos da lista (do início para o fim), utilizaremos a seguinte função:
void imprime_lista(Lista *li){ /*caso a lista esteja vazia*/!!"); if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ aux = li->inicio; do{ /*impressão do elemento que aux aponta*/ printf(" %d ", aux->num); //*aux aponta para o próximo elemento da lista, que será o endereço contido no ponteiro prox.*/ aux = aux->prox; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem impressos*/ }while(aux != NULL); } getch(); }
A saída seria: 9 3 6 2.
Para removermos um determinado elemento da lista, utilizaremos a seguinte função:
void remover_elemento(Lista *li){ int numero; /*a variável achou será utilizada como um contador de números removidos*/ int achou; /*caso a lista esteja vazia*/ if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ printf("Digite o elemento a ser removido: "); scanf("%d", &numero); /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ aux = li->inicio; /*utilizando o ponteiro ele, fazemos com ele aponte para NULL*/ anterior = NULL; achou = 0; do{ /*caso aux-> num seja igual ao número a ser removido*/ if(aux->num == numero){ /*incrementamos achou*/ achou = achou + 1; /*se o elemento a ser removido for o primeiro da lista*/ if(aux == li->inicio){ /*inicio apontará para o segundo elemento da lista ou para NULL caso o elemento removido seja o único elemento da lista*/ li->inicio = aux ->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux aponta para o inicio da lista*/ aux = li->inicio; /*se o elemento a ser removido for o último da lista*/ }else if (aux == li->fim){ /*o elemento anterior a fim, no atributo prox apontará para NULL*/ anterior->prox = NULL; /*fim aponta para o elemento apontado por anterior*/ li->fim = anterior; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*como era o últmo elemento da lista, aux recebe NULL*/ aux = NULL; /*se o elemento a ser removido não for nem o primeiro nem o último da lista */ }else{ /*o elemento anterior ao elemento a ser removido, no atributo prox apontará para o elemento para qual aux->prox apontava*/ anterior->prox = aux->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux aponta para o próximo elemento da lista, aquele que era o seguinte ao número removido*/ aux = anterior -> prox; } /*caso aux-> num não seja igual ao número a ser removido*/ }else{ anterior = aux; aux = aux -> prox; } /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem pesquisados*/ }while(aux != NULL); /*impressão do resultado*/ if(achou == 0){ printf("Numero nao encontrado!"); }else{ printf("Numero removido %d vez(es)",achou); } } getch(); }
Com base na lista criada anteriormente, faremos algumas remoções:
Primeiramente, vamos remover o número 3:
E depois removeremos o número 9.
Nesta última operação esvaziaremos a nossa lista, isto significa remover todos os seus nós restantes desalocando o espaço reservado para cada um. Esta é a implementação utilizada:
void esvaziar_lista(Lista *li){ /*caso a lista esteja vazia*/ if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço de inicio aponta*/ aux = li->inicio; do{ /*inicio apontará para o próximo elemento da lista*/ li->inicio = li->inicio->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux apontará para o mesmo endereço que inicio aponta*/ aux = li->inicio; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem removidos*/ }while(aux != NULL); printf("\nLista Esvaziada!!"); } getch(); }
O resultado final após essa operação seria esse:
A diferença desse tipo de lista simplesmente encadeada é que ela utiliza determinado dado armazenado como parâmetro para a ordenação da lista. No nosso caso utilizaremos "num" para ordenar nossa lista de maneira crescente.
Para este tipo de lista realizaremos 4 operações:
Esta é a implementação da função que utilizaremos para inserir um dado no início da lista.
void insere_lista(Lista *li){ /*a cada inserção alocamos dinamicamente um espaço para um novo nó*/ No *novo =(No*) malloc(sizeof(No)); /*o número a ser inserido será armazenado em novo->num*/ printf("\nDigite o no a ser inserido na lista: "); scanf("%d",&novo->num); /*caso a lista estiver vazia o primeiro elemento a ser inserido será o primeiro e último*/ if(li->inicio == NULL){ li->inicio = novo; /*aqui fazemos com que inicio aponte para o mesmo endereço que novo aponta*/ li->fim = novo; /*aqui fazemos com que fim aponte para o mesmo endereço que novo aponta*/ li->fim->prox = NULL; /*aqui fazemos com que o endereço para o qual fim aponta, no atributo prox receba NULL*/ /*caso a lista não esteja vazia*/ }else{ anterior = NULL; /*inicialmente anterior apontará para NULL*/ aux = li->inicio; /*aux aponta para o primeiro elemento da lista*/ /*enquanto aux apontar para um nó existente e o número inserido for maior que o número apontado por aux, a variação do valor de aux fará com que o novo número possa ser inseirido no local adequado, que é antes de um número maior que ele.*/ while(aux !=NULL && novo->num > aux->num){ anterior = aux; /*anterior aponta para o endereço que aux aponta*/ aux = aux->prox; /*aux aponta para o próximo nó da lista*/ } /*caso não exista nenhum número menor que o novo número*/ if(anterior == NULL){ novo->prox = li->inicio; /*o novo elemento no atributo prox, apontará para o elemento que até então era o primeiro elemento da lista*/ li->inicio = novo; /*novo será o primeiro elemento da lista, inicio apontará para o endereço de novo*/ /*caso não exista nenhum número maior que o novo número*/ }else if(aux == NULL){ li->fim->prox = novo; /*o até então ultimo elemento da lista no atributo prox apontará para novo*/ li->fim = novo; /*novo será o ultimo elemento da lista, fim apontará para o endereço de novo*/ li->fim->prox = NULL; /*aqui fazemos com que o endereço para o qual fim aponta, no atributo prox receba NULL*/ /*caso número precise ser inseirido no meio da lista*/ }else{ anterior->prox = novo; /*o primeiro número menor que o novo inseirido no atributo prox recebe o endereço de novo*/ novo->prox = aux; /*novo no atibuto prox, recebe o endereço do primeiro número maior que ele*/ } } printf("\nNumero inserido na lista!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos os ponteiros inicio e fim apontados para null:
Primeiro: inseriremos o número 3 na lista.
Segundo: inseriremos o número 9 na lista.
Terceiro: inseriremos o número 6 na lista.
Quarto: inseriremos o número 2 na lista.
Para imprimir os elementos da lista (do início para o fim), utilizaremos a seguinte função:
void imprime_lista(Lista *li){ /*caso a lista esteja vazia*/!!"); if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ aux = li->inicio; do{ /*impressão do elemento que aux aponta*/ printf(" %d ", aux->num); //*aux aponta para o próximo elemento da lista, que será o endereço contido no ponteiro prox.*/ aux = aux->prox; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem impressos*/ }while(aux != NULL); } getch(); }
A saída seria: 2 3 6 9.
Para removermos um determinado elemento da lista, utilizaremos a seguinte função:
void remover_elemento(Lista *li){ int numero; /*a variável achou será utilizada como um contador de números removidos*/ int achou; /*caso a lista esteja vazia*/ if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ printf("Digite o elemento a ser removido: "); scanf("%d", &numero); /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ aux = li->inicio; /*utilizando o ponteiro ele, fazemos com ele aponte para NULL*/ anterior = NULL; achou = 0; do{ /*caso aux-> num seja igual ao número a ser removido*/ if(aux->num == numero){ /*incrementamos achou*/ achou = achou + 1; /*se o elemento a ser removido for o primeiro da lista*/ if(aux == li->inicio){ /*inicio apontará para o segundo elemento da lista ou para NULL caso o elemento removido seja o único elemento da lista*/ li->inicio = aux ->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux aponta para o inicio da lista*/ aux = li->inicio; /*se o elemento a ser removido for o último da lista*/ }else if (aux == li->fim){ /*o elemento anterior a fim, no atributo prox apontará para NULL*/ anterior->prox = NULL; /*fim aponta para o elemento apontado por anterior*/ li->fim = anterior; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*como era o últmo elemento da lista, aux recebe NULL*/ aux = NULL; /*se o elemento a ser removido não for nem o primeiro nem o último da lista */ }else{ /*o elemento anterior ao elemento a ser removido, no atributo prox apontará para o elemento para qual aux->prox apontava*/ anterior->prox = aux->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux aponta para o próximo elemento da lista, aquele que era o seguinte ao número removido*/ aux = anterior -> prox; } /*caso aux-> num não seja igual ao número a ser removido*/ }else{ anterior = aux; aux = aux -> prox; } /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem pesquisados*/ }while(aux != NULL); /*impressão do resultado*/ if(achou == 0){ printf("Numero nao encontrado!"); }else{ printf("Numero removido %d vez(es)",achou); } } getch(); }
Com base na lista criada anteriormente, faremos algumas remoções:
Vamos então remover o número 6:
Também removeremos o número 2.
Por fim removeremos o número 9.
Nesta última operação esvaziaremos a nossa lista, isto significa remover todos os seus nós restantes desalocando o espaço reservado para cada um. Esta é a implementação utilizada:
void esvaziar_lista(Lista *li){ /*caso a lista esteja vazia*/ if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço de inicio aponta*/ aux = li->inicio; do{ /*inicio apontará para o próximo elemento da lista*/ li->inicio = li->inicio->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux apontará para o mesmo endereço que inicio aponta*/ aux = li->inicio; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem removidos*/ }while(aux != NULL); printf("\nLista Esvaziada!!"); } getch(); }
O resultado final após essa operação seria esse:
Assim como as listas simplesmente encadeadas, uma lista duplamente encadeada é uma estrutura de dados que representa um conjunto de dados organizados em ordem linear e dinâmica. Ela também é composta por células ou nós (nomenclatura adotada), no entanto, a conexão entre os seus elementos é feita através de dois ponteiros (um que aponta para o elemento anterior, e o outro, para o seguinte).
Numa lista duplamente encadeada, para cada novo elemento inserido na estrutura, alocamos um espaço de memória para armazená-lo. Desta forma, o espaço total de memória gasto pela estrutura é proporcional ao número de elementos nela armazenado. No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo, portanto não temos acesso direto aos elementos da lista. Para que seja possível percorrer todos os elementos da lista, devemos explicitamente guardar o encadeamento dos elementos, o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro para o próximo elemento da lista e um ponteiro para o elemento anterior.
Características a destacar:
Para representarmos um elemento da lista (um nó) vamos utilizar uma struct, que chamaremos de No. Vejamos:
struct No{ int num; struct No *prox; struct No *ant; }; typedef struct No No;
Cada nó de uma lista duplamente encadeada irá possuir pelo menos (pode ser mais de um) um atributo que corresponde determinado dado a ser armazenado pela lista (int, float, char, struct..), um ponteiro (do tipo No) *prox que será utilizado para armazenar o endereço de memória do próximo nó e outro ponteiro (do tipo No) *ant que será utilizado para armazenar o endereço de memória do nó anterior (dessa maneira "ligamos" duas vezes um nó a outro nó). Aqui utilizaremos uma lista para armazenar inteiros (int num).
Para o controle da lista utilizaremos uma estrutura do tipo Lista. Ela contém dois ponteiros do tipo No (inicio e fim), que irão armazenar os endereço de memória do primeiro e do último elemento da lista respectivamente.
/*registro do tipo Lista contento dois ponteiros do tipo nó para controlar a lista*/ struct Lista{ struct No *inicio; /*aponta para o elemento do início da lista*/ struct No *fim; /*aponta para o elemento do fim da lista*/ }; typedef struct Lista Lista;
Para auxiliar em algumas funções, é necessário utilizar três ponteiros auxiliares do tipo No. Então definimos abaixo:
/*necessitaremos também de três ponteiros auxilares *aux , *aux2 e *anterior */
No *aux;
No *aux2;
No *anterior;
Nesse ponto definiremos também uma função cria_lista( ). Ela será utilizada para criar uma lista, ou seja, alocará dinamicamente o espaço necessário para armazenar seus ponteiros (inicio e fim ) e irá inicializá-los com NULL. Isso indica que a lista inicialmente está vazia.
Lista* cria_lista(){
/*alocação do ponteiro li para controlar a lista*/
Lista* li = (Lista*) malloc(sizeof(Lista));
if(li != NULL){
/*Se a lista está inicialmente vazia, inicio e fim apontam para NULL */
li->fim = NULL;
li->inicio = NULL;
}
return li;
}
Na função main, devemos definir um ponteiro do tipo Lista. Ele irá receber o endereço do espaço alocado pela função cria_lista( ) e também servirá de parâmetro para as demais funções seguintes.
int main(){ Lista *li = cria_lista(); ...blocos de chamada de função... return 0; }
Como o próprio nome descreve é uma lista duplamente encadeada em que não há qualquer tipo de ordenação em relação aos nós pertencentes à lista. A disposição dos mesmos dependerá da ordem e local (início ou fim da lista) em que forem inseridos.
Para este tipo de lista realizaremos 6 operações:
Esta é a implementação da função que utilizaremos para inserir um dado no início da lista.
void insere_inicio_lista(Lista *li){ /*a cada inserção alocamos dinamicamente um espaço para um novo nó*/ No *novo =(No*) malloc(sizeof(No)); /*o número a ser inserido será armazenado em novo->num*/ printf("Digite o numero a ser inserido no inicio da lista: "); scanf("%d",&novo->num); /*caso a lista estiver vazia o primeiro elemento a ser inserido será o primeiro e último elemento da lista*/ if(li->inicio == NULL){ li->inicio = novo; /*aqui fazemos com que inicio aponte para o mesmo endereço que novo aponta*/ li->fim = novo; /*aqui fazemos com que fim aponte para o mesmo endereço que novo aponta*/ /*como será o único elemento da lista, novo->prox e novo->ant apontam para null*/ novo->prox = NULL; novo->ant = NULL; /*caso a lista não esteja vazia*/ }else{ /*como a inserção é no inicio, o novo nó inserido receberá no atributo prox (seu ponteiro que aponta para o próximo nó) o endereço que inicio aponta*/ novo->prox = li->inicio; /*inicio no atributo ant recebe o endereço de novo, aqui ainda inicio não foi alterado, portanto essa linha é necessária para que quando for o segundo da lista este elemento possa apontar (através de ant) para o novo elemento que se tornará o novo inicio*/ li->inicio->ant = novo; /*novo no atributo ant recebe null, como depois se tornará o primeiro elemento da lista, seu ponteiro que aponta para o nó anterior será null*/ novo->ant = NULL; /*aqui inicio apontará para o novo nó inserido*/ li->inicio = novo; } printf("\nNumero inserido na lista!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos os ponteiros inicio e fim apontados para null:
Agora inseriremos o número 8 no início da lista.
Depois vamos inserir o número 9 no início da lista.
Agora trataremos de inserir dados no fim da lista. Vejamos a implementação:
void insere_fim_lista(Lista *li){ /*a cada inserção alocamos dinamicamente um espaço para um novo nó*/ No *novo =(No*) malloc(sizeof(No)); /*o número a ser inserido será armazenado em novo->num*/ printf("Digite o numero a ser inserido no fim da lista: "); scanf("%d,&novo->num); /*caso a lista estiver vazia o primeiro elemento a ser inserido será o primeiro e último elemento da lista*/ if( li->inicio == NULL){ li->inicio = novo; /*aqui fazemos com que inicio aponte para o mesmo endereço que novo aponta*/ li->fim = novo; /*aqui fazemos com que fim aponte para o mesmo endereço que novo aponta*/ /*como será o único elemento da lista, novo->prox e novo->ant apontam para null*/ novo->prox = NULL; novo->ant = NULL; }else{ /*fim no atributo prox recebe o endereço de novo, aqui ainda fim não foi alterado, portanto essa linha é necessária para quando esse elemento vier a ser o penultimo da lista possa apontar para o novo elemento que se tonará o novo fim*/ li->fim->prox = novo; /*como a inserção é no fim, o novo nó inserido receberá no atributo ant(seu ponteiro que aponta para o nó anterior) o atual endereço que fim aponta*/ novo->ant = li->fim; /*como será o ultimo elemento da lista, novo no atributo prox apontará para null*/ novo->prox = NULL; /*fim aponta para o novo nó inserido*/ li->fim = novo; } printf("\nNumero inserido na lista!"); getch(); }
Complementando a lista iniciada anteriormente, vamos inserir o número 3 no final da lista:
Por fim, vamos inserir o número 5 no final da lista:
Para imprimir os elementos da lista (do início para o fim), utilizaremos a seguinte função:
void imprime_lista_inicio_ao_fim(Lista *li){ /*caso a lista esteja vazia*/ if( li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ aux = li->inicio; do{ /*impressão do elemento que aux aponta*/ printf(" %d ", aux->num); /*aux aponta para o próximo elemento da lista, que será o endereço contido no ponteiro prox.*/ aux = aux->prox; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem impressos*/ }while(aux != NULL); } getch(); }
A saída seria: 9 8 3 5.
Para imprimir os elementos da lista (do fim para o início), utilizaremos a seguinte função:
void imprime_lista_fim_ao_inicio(Lista *li){ /*caso a lista esteja vazia*/ if( li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que fim aponta*/ aux = li->fim; do{ /*impressão do elemento que aux aponta*/ printf(" %d ", aux->num); /*aux aponta para o elemento anterior da lista, que será o endereço contido no ponteiro ant.*/ aux = aux->ant; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem impressos*/ }while(aux != NULL); } getch(); }
A saída seria: 5 3 8 9.
Para removermos um determinado elemento da lista, utilizaremos a seguinte função:
void remover_elemento(Lista *li){ int numero, achou; /*a variável achou será utilizada como um contador de números removidos*/ if(li->inicio == NULL){ /*caso a lista esteja vazia*/ printf("\nLista Vazia!!"); }else{ /*caso a lista não esteja vazia*/ printf("Digite o elemento a ser removido: "); scanf("%d", &numero); aux = li->inicio; /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ achou = 0; do{ if(aux->num == numero){ /*caso aux-> num seja igual ao número a ser removido*/ achou = achou + 1; /*incrementamos achou*/ if(aux == li->inicio){ /*se o elemento a ser removido for o primeiro da lista*/ li->inicio = aux ->prox; /*inicio apontará para o segundo elemento da lista ou para NULL caso o elemento removido seja o único elemento da lista*/ if( li->inicio != NULL){ /*caso inicio tenha não recebido null na linha anterior*/ li->inicio->ant = NULL; /*ant de inicio também apontará para null*/ } free(aux); /*desalocamos o espaço para onde aux apontava*/ aux = li->inicio; /*aux aponta para o inicio da lista*/ }else if(aux == li->fim){ /*se o elemento a ser removido for o ultimo da lista*/ li->fim = li->fim->ant; /*fim apontará para o elemento anterior a ele*/ li->fim->prox = NULL; /*fim no atributo prox apontará para null*/ free(aux); /*desalocamos o espaço para onde aux apontava*/ aux = NULL; /*como era o últmo elemento da lista, aux recebe NULL*/ }else{ /*se o elemento a ser removido não for nem o primeiro nem o último da lista */ aux->ant->prox = aux->prox; /*o elemento anterior ao que iremos remover, em prox, apontara para o endereço do próximo elemento depois de aux */ aux->prox->ant = aux->ant; /*o elemento seguinte ao que iremos remover, em ant, apontará para o endereço do elemento anterior a aux */ aux2 = aux->prox; /*aux2 aponta para o elemento depois de aux*/ free(aux); /*desalocamos o espaço para onde aux apontava*/ aux = aux2; /*aux aponta para onde aux2 apontava*/ } }else{ /*caso aux-> num não seja igual ao número a ser removido*/ aux = aux -> prox; /*aux aponta para o próximo elemento da lista*/ } /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem pesquisados*/ }while(aux != NULL); /*impressão do resultado*/ if(achou == 0){ printf("Numero nao encontrado!"); }else{ printf("Numero removido %d vez(es)",achou); } } getch(); }
Com base na lista criada anteriormente, faremos algumas remoções:
Primeiramente, vamos remover o número 9:
Vamos então remover o número 3:
Por fim removeremos o número 8.
Nesta última operação esvaziaremos a nossa lista, isto significa remover todos os seus nós restantes desalocando o espaço reservado para cada um. Esta é a implementação utilizada:
void esvaziar_lista(Lista *li){ /*caso a lista esteja vazia*/ if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço de inicio aponta*/ aux = li->inicio; do{ /*inicio apontará para o próximo elemento da lista*/ li->inicio = li->inicio->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux apontará para o mesmo endereço que inicio aponta*/ aux = li->inicio; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem removidos*/ }while(aux != NULL); printf("\nLista Esvaziada!!"); } getch(); }
O resultado final após essa operação seria esse:
A diferença desse tipo de lista duplamente encadeada é que ela utiliza determinado dado armazenado como parâmetro para a ordenação da lista. No nosso caso utilizaremos "num" para ordenar nossa lista de maneira crescente.
Para este tipo de lista realizaremos 5 operações:
Esta é a implementação da função que utilizaremos para inserir um dado na lista.
void insere_lista(Lista *li){ No *novo =(No*) malloc(sizeof(No)); /*a cada inserção alocamos dinamicamente um espaço para um novo nó*/ /*o número a ser inserido será armazenado em novo->num*/ printf("Digite o numero a ser inserido na lista: "); scanf("%d",&novo->num); if(li->inicio == NULL){ /*caso a lista estiver vazia o elemento a ser inserido será o primeiro e último elemento da lista*/ /*como será o único elemento da lista, novo->prox e novo->ant apontam para null*/ novo->prox = NULL; novo->ant = NULL; li->inicio = novo; /*aqui fazemos com que inicio aponte para o mesmo endereço que novo aponta*/ li->fim = novo; /*aqui fazemos com que fim aponte para o mesmo endereço que novo aponta*/ }else{ /*caso a lista não esteja vazia*/ aux = li->inicio; /*aux aponta para o endereço que inicio aponta*/ /*enquanto ainda houverem elementos na lista e o novo número for maior que aux->num, ou seja enquanto não for encontrado um número maior que o número inserido*/ while(aux != NULL && novo->num > aux->num){ aux = aux->prox; /*aux aponta para o próximo elemento da lista*/ /*isso é feito para encontrar o ponto exato para o número ser inserido*/ } /*caso não existam números maiores ou iguais ao novo número , ele será inserido no início da lista*/ if(aux == li->inicio){ novo->prox = li->inicio; /*novo->prox apontara para o atual inicio, que depois será o segundo elemento*/ novo->ant = NULL; /*como novo será o primeiro da lista, seu ponteiro ant deverá apontar para null*/ li->inicio->ant = novo; /*o inicio atual(que depois será o segunda da lista) em ant, apontara para o endereço de novo*/ li->inicio = novo; /*inicio aponta para novo*/ /*caso todos elementos da lista sejam menores que o número a ser inserido, ele será inserido no fim*/ }else if(aux == NULL){ li->fim->prox = novo; /*o fim atual (que depois será o penultimo da lista) em prox, apontará para novo*/ novo->ant = li->fim; /*novo -> ant aponta para o endereço do fim atual.*/ li->fim = novo; /*fim aponta para novo*/ li->fim->prox = NULL; /*todo ultimo elemento da lista em prox aponta para null*/ }else{ /*caso novo seja inserido no meio da lista, ele será inserido antes de aux*/ novo->prox = aux; /*novo será inserido antes do aux atual, então novo->prox aponta para o aux atual*/ aux->ant->prox = novo; /*o número que estava antes de aux em prox aponta para novo*/ novo->ant = aux->ant; /*novo-> ant aponta para o nó anterior a aux atual*/ aux->ant = novo; /*aux atual será o elemento seguinte a novo, portanto em ant apontará para novo*/ } } printf("\nNumero inserido na lista!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos os ponteiros inicio e fim apontados para null:
Primeiro: inseriremos o número 5 na lista.
Segundo: vamos inserir o número 9 na lista.
Terceiro: vamos inserir o número 2 na lista:
Por fim, vamos inserir o número 7 na lista:
Para imprimir os elementos da lista (do início para o fim), utilizaremos a seguinte função:
void imprime_lista_inicio_ao_fim(Lista *li){ /*caso a lista esteja vazia*/ if( li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ aux = li->inicio; do{ /*impressão do elemento que aux aponta*/ printf(" %d ", aux->num); /*aux aponta para o próximo elemento da lista, que será o endereço contido no ponteiro prox.*/ aux = aux->prox; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem impressos*/ }while(aux != NULL); } getch(); }
A saída seria: 2 5 7 9.
Para imprimir os elementos da lista (do fim para o início), utilizaremos a seguinte função:
void imprime_lista_fim_ao_inicio(Lista *li){ /*caso a lista esteja vazia*/ if( li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que fim aponta*/ aux = li->fim; do{ /*impressão do elemento que aux aponta*/ printf(" %d ", aux->num); /*aux aponta para o elemento anterior da lista, que será o endereço contido no ponteiro ant.*/ aux = aux->ant; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem impressos*/ }while(aux != NULL); } getch(); }
A saída seria: 9 7 5 2.
Para removermos um determinado elemento da lista, utilizaremos a seguinte função:
void remover_elemento(Lista *li){ int numero, achou; /*a variável achou será utilizada como um contador de números removidos*/ if(li->inicio == NULL){ /*caso a lista esteja vazia*/ printf("\nLista Vazia!!"); }else{ /*caso a lista não esteja vazia*/ printf("Digite o elemento a ser removido: "); scanf("%d", &numero); aux = li->inicio; /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço que inicio aponta*/ achou = 0; do{ if(aux->num == numero){ /*caso aux-> num seja igual ao número a ser removido*/ achou = achou + 1; /*incrementamos achou*/ if(aux == li->inicio){ /*se o elemento a ser removido for o primeiro da lista*/ li->inicio = aux ->prox; /*inicio apontará para o segundo elemento da lista ou para NULL caso o elemento removido seja o único elemento da lista*/ if( li->inicio != NULL){ /*caso inicio tenha não recebido null na linha anterior*/ li->inicio->ant = NULL; /*ant de inicio também apontará para null*/ } free(aux); /*desalocamos o espaço para onde aux apontava*/ aux = li->inicio; /*aux aponta para o inicio da lista*/ }else if(aux == li->fim){ /*se o elemento a ser removido for o ultimo da lista*/ li->fim = li->fim->ant; /*fim apontará para o elemento anterior a ele*/ li->fim->prox = NULL; /*fim no atributo prox apontará para null*/ free(aux); /*desalocamos o espaço para onde aux apontava*/ aux = NULL; /*como era o últmo elemento da lista, aux recebe NULL*/ }else{ /*se o elemento a ser removido não for nem o primeiro nem o último da lista */ aux->ant->prox = aux->prox; /*o elemento anterior ao que iremos remover, em prox, apontara para o endereço do próximo elemento depois de aux */ aux->prox->ant = aux->ant; /*o elemento seguinte ao que iremos remover, em ant, apontará para o endereço do elemento anterior a aux */ aux2 = aux->prox; /*aux2 aponta para o elemento depois de aux*/ free(aux); /*desalocamos o espaço para onde aux apontava*/ aux = aux2; /*aux aponta para onde aux2 apontava*/ } }else{ /*caso aux-> num não seja igual ao número a ser removido*/ aux = aux -> prox; /*aux aponta para o próximo elemento da lista*/ } /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem pesquisados*/ }while(aux != NULL); /*impressão do resultado*/ if(achou == 0){ printf("Numero nao encontrado!"); }else{ printf("Numero removido %d vez(es)",achou); } } getch(); }
Com base na lista criada anteriormente, faremos algumas remoções:
Primeiramente, vamos remover o número 5 da nossa lista:
Depois removeremos o número 9.
E por fim removeremos o número 2.
Nesta última operação esvaziaremos a nossa lista, isto significa remover todos os seus nós restantes desalocando o espaço reservado para cada um. Esta é a implementação utilizada:
void esvaziar_lista(Lista *li){ /*caso a lista esteja vazia*/ if(li->inicio == NULL){ printf("\nLista Vazia!!"); /*caso a lista não esteja vazia*/ }else{ /*utilizando o ponteiro aux, fazemos com ele aponte para o mesmo endereço de inicio aponta*/ aux = li->inicio; do{ /*inicio apontará para o próximo elemento da lista*/ li->inicio = li->inicio->prox; /*desalocamos o espaço para onde aux apontava*/ free(aux); /*aux apontará para o mesmo endereço que inicio aponta*/ aux = li->inicio; /*essa operação será feita até aux ser diferente de NULL, ou seja, não houverem mais elementos a serem removidos*/ }while(aux != NULL); printf("\nLista Esvaziada!!"); } getch(); }
O resultado final após essa operação seria esse:
As listas citadas anteriormente também podem ser implementadas de forma circular. Isso significa que, quando forem simplesmente encadeadas seu ponteiro próximo “*prox” do último elemento apontará para o primeiro elemento da lista. Já quando forem duplamente encadeadas terão além do ponteiro próximo “*prox” do último elemento apontando para o primeiro elemento da lista, o ponteiro anterior “*ant” do primeiro elemento apontará para o último elemento da lista.
