<aside>
Conhecimentos necessários:
Alocação de memória (ponteiros)
</aside>
<aside>
Navegação
</aside>
Já imaginou fazer um programa que receba uma lista de compras? Tipo, parece simples, né? Basta usar um array e dá certo… bom, sim, pode dar dar certo, mas concorda comigo que nunca será quantos itens a pessoa colocará, então você teria que criar um array muito grande para que ela possa adicionar os itens que ela pretende comprar… concorda comigo que isso não parece eficiente? Imagina criar um array de 100 itens para a pessoa adicionar apenas 5? É perda de memória! Ou simplesmente fazer um array de 100 itens e a pessoa querer adicionar 300… também não dá, né? Isso não é eficiente e menos ainda prático… Isso porque eu nem mencionei a retirada fora de ordens de itens…
Para resolver esse problema, usaremos listas!
Listas são estruturas de dados que não permitem adicionar quantos itens quisermos em qualquer lugar dela! Podemos adicionar no final, no início ou no meio e retirar tudo de uma forma bem fácil e prática.
Isso porque ela funciona a partir de TADs (tipo abstrato de dados)
Nada mais é do que uma struct que contém os dados que precisamos e - aí que entra o ponto principal - um ponteiro para outra struct idêntica e do mesmo tipo.
Imagino que talvez já tenha sacado o que vai acontecer aqui… caso não, vou te explicar: esse ponteiro nas structs vamos usar para conectar uma na outra e, quanto todas estiverem ligadas, teremos uma lista!
Algo parecido com isso:
Está vendo? Há um ponteiro indicando o início do primeiro elemento, que mostra onde fica o próximo, que mostra onde fica o próximo e assim vai… até chegar no último elemento, que não aponta pra ninguém, pois ele é o último, então seu ponteiro é nulo.
Para criar cada um desses itens em quadradinho que apontam para o próximo, precisamos criá-los dinamicamente, ou seja, usando alocação de memória… então como bem sabe, se perdermos o ponteiro no início (ou qualquer outro) em algum momento, perdemos toda a lista (ou parte dela, no caso de perdermos onde aponta o ponteiro de algum dos elementos).
Na lista, você pode adicionar elementos em três lugares diferentes:
Para adicionar um elemento no início, basta criá-lo, apontar para o primeiro elemento e fazer o ponteiro do início apontar para ele. Tipo assim:
#include <stdlib.h>
typedef struct elem {
int valor;
struct elem *proximo;
} elem;
void AdicionarNoInicio(elem **inicio, int value){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
elemento_criado->proximo = *inicio; //atribuindo o ex-primeiro elemento como o próximo
*inicio = elemento_criado; //mudando o início para o elemento que acabamos de criar
}
int main()
{
elem *inicio = NULL; //inicializando o ponteiro
AdicionarNoInicio(&inicio, 18); //colocando o elemento 18 no início da lista
return 0;
}
Observe que temos que modificar o valor original do ponteiro, por isso criamos um ponteiro de ponteiro nos parâmetros da função
Para adicionar um elemento no meio de outros dois elementos (que chamarei de A e B para facilitar), basta criá-lo e apontar para o elemento B, depois disso fazer o elemento A apontar para o que acabamos de criar. Tipo assim:
#include <stdlib.h>
typedef struct elem {
int valor;
struct elem *proximo;
} elem;
void AdicionarNoMeio(elem **inicio, int value, int local){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
if(!*inicio){ //verifica se a lista está vazia ao colocar um elemento.
*inicio = elemento_criado;
}
else{
elem* auxiliar = *inicio;
for(int i = 1; i < local-1; i++){ //pegando o elemento anterior ao local onde vamos colocar
if(auxiliar->proximo) //verifica se existe um próximo elemento. Caso não exista, esse é o último elemento
auxiliar = auxiliar->proximo;
else
break;
}
if(auxiliar->proximo){ //se não for o último elemento...
elemento_criado->proximo = auxiliar->proximo;
auxiliar->proximo = elemento_criado;
}
else{ //se for o último elemento...
auxiliar->proximo = elemento_criado;
}
}
}
int main()
{
elem *inicio = NULL; //inicializando o ponteiro
AdicionarNoMeio(&inicio, 18, 3); //colocando o elemento 18 no terceiro lugar
return 0;
}
Basicamente o que está acontecendo aqui é o seguinte… pensa comigo: para adicionar o elemento no terceiro lugar, precisamos colocar na frente do segundo, então basta pegarmos o segundo elemento, apontar o elemento que criamos para o ex-terceiro e o apontar o segundo para o elemento que acabamos de criar. Assim, adicionamos um novo elemento entre o segundo e o terceiro. O problema é que ele começa logo pegando o primeiro elemento, então para resolver isso, basta colocar local-1 dentro do for.
Para não dar problema caso a função esteja vazia, há uma verificação no início para verificar se o ponteiro do início é nulo.
Para também evitar de dar problema caso a pessoa digite um local maior do que a lista, há uma verificação para garantir que o próximo elemento existe e, caso não exista, ele adicione no final normalmente.
Para adicionar no final, basta percorrer a lista até chegar no final e adicionar o elemento logo em seguida. Tipo assim:
#include <stdlib.h>
typedef struct elem {
int valor;
struct elem *proximo;
} elem;
void AdicionarNoFinal(elem **inicio, int value){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
if(!*inicio){ //verifica se a lista está vazia ao colocar um elemento.
*inicio = elemento_criado;
}
else{
elem* auxiliar = *inicio;
while(auxiliar->proximo){ //vai percorrendo a lista até achar um elemento que não tem um próximo, ou seja, é o último.
auxiliar = auxiliar->proximo;
}
auxiliar->proximo = elemento_criado;
}
}
int main()
{
elem *inicio = NULL; //inicializando o ponteiro
AdicionarNoFinal(&inicio, 18); //colocando o elemento 18 no final da lista
return 0;
}
Para remover o primeiro elemento é bem tranquilo! Bastante salvar o primeiro elemento em um ponteiro, fazer o início apontar para o segundo elemento e limpar da memória o ex-primeiro elemento que queremos apagar. Prontinho! Só não esqueça de verificar se a lista não está vazia!
Fazendo isso em uma função, ficará assim:
void RemoverNoInicio(elem **inicio){
if(*inicio){ //verifica se início não é nulo, ou seja, se a lista não é vazia
elem *aux = *inicio; //salvamos o primeiro elemento para depois limpá-lo da memória
*inicio = (*inicio)->proximo; //pega o segundo elemento da lista
free(aux); //limpa o primeiro elemento da memória para excluí-lo
}
}
Para remover no meio, vamos usar uma lógica parecida para adicionar um elemento no meio: se queremos remover um elemento, vamos pegar o anterior a ele e fazer 3 coisas:
Por exemplo: suponha que tenho a seguinte lista:
Se eu quero apagar o terceiro elemento, eu vou pegar o elemento 22, salvar o elemento 33, e fazer o próximo do 22 ser o 44, ficando assim:
Salvo: 33
Como esse 33 ainda está ocupando memória, basta apagar ele usando o free();
Colocando isso em prática em uma função, fica assim:
void RemoverNoMeio(elem **inicio, int local){
if(*inicio){ //verifica se início não é nulo, ou seja, se a lista não é vazia
elem* aux = *inicio;
for(int i = 1; i < local-1; i++){ //pegando o elemento anterior do elemento que vamos apagar
if(aux->proximo) //se existir um próximo elemento ainda...
aux = aux->proximo; //...vá para esse próximo...
else //...caso não exista...
break; //...pare
}
if(aux->proximo) { //se existir um próximo elemento...
elem *apagar = aux->proximo; //...salve-o em uma variável para depois apagar...
aux->proximo = aux->proximo->proximo; //..., coloque que o próximo será o elemento seguinte do que vamos apagar...
free(apagar); //...e apague o elemento
}
}
}
Para remover o último elemento, basta a gente pegar o penúltimo e limpar o próximo elemento. Pegamos o penúltimo porque se pegássemos o último elemento, quando limparmos ele, não teríamos como colocar o ponteiro de próximo do elemento anterior como nulo. Mas não podemos esquecer de verificar se a lista está vazia ou se possui apenas um elemento.
Escrevendo isso em uma função, fica assim:
void RemoverNoFinal(elem **inicio){
if(*inicio) { //verifica se início não é nulo, ou seja, se a lista não é vazia
if(!(*inicio)->proximo) { //se o primeiro elemento não tiver um próximo...
free(*inicio); //...apague o primeiro e único elemento...
*inicio = NULL; //...e coloque o inicio como NULL...
}
else{ //...caso contrário...
elem *aux = *inicio; //...comece no início...
while (aux->proximo->proximo){ //...e percorra até pegar o penúltimo elemento...
aux = aux->proximo;
}
free(aux->proximo); //...limpe o elemento seguite do penúltimo...
aux->proximo = NULL; //...e defina-o como nulo
}
}
}
Adicionando tudo isso em um código simples, temos:
#include <stdio.h>
#include <stdlib.h>
typedef struct elem {
int valor;
struct elem *proximo;
} elem;
void AdicionarNoInicio(elem **inicio, int value){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
elemento_criado->proximo = *inicio; //atribuindo o ex-primeiro elemento como o próximo
*inicio = elemento_criado; //mudando o início para o elemento que acabamos de criar
}
void AdicionarNoMeio(elem **inicio, int value, int local){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
if(!*inicio){ //verifica se a lista está vazia ao colocar um elemento.
*inicio = elemento_criado;
}
else{
elem* auxiliar = *inicio;
for(int i = 1; i < local-1; i++){ //pegando o elemento anterior ao local onde vamos colocar
if(auxiliar->proximo) //verifica se existe um próximo elemento. Caso não exista, esse é o último elemento
auxiliar = auxiliar->proximo;
else
break;
}
if(auxiliar->proximo){ //se não for o último elemento...
elemento_criado->proximo = auxiliar->proximo;
auxiliar->proximo = elemento_criado;
}
else{ //se for o último elemento...
auxiliar->proximo = elemento_criado;
}
}
}
void AdicionarNoFinal(elem **inicio, int value){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
if(!*inicio){ //verifica se a lista está vazia ao colocar um elemento.
*inicio = elemento_criado;
}
else{
elem* auxiliar = *inicio;
while(auxiliar->proximo){ //vai percorrendo a lista até achar um elemento que não tem um próximo, ou seja, é o último.
auxiliar = auxiliar->proximo;
}
auxiliar->proximo = elemento_criado;
}
}
void RemoverNoInicio(elem **inicio){
if(*inicio){ //verifica se início não é nulo, ou seja, se a lista não é vazia
elem *aux = *inicio; //salvamos o primeiro elemento para depois limpá-lo da memória
*inicio = (*inicio)->proximo; //pega o segundo elemento da lista
free(aux); //limpa o primeiro elemento da memória para excluí-lo
}
}
void RemoverNoMeio(elem **inicio, int local){
if(*inicio){ //verifica se início não é nulo, ou seja, se a lista não é vazia
elem* aux = *inicio;
for(int i = 1; i < local-1; i++){ //pegando o elemento anterior do elemento que vamos apagar
if(aux->proximo) //se existir um próximo elemento ainda...
aux = aux->proximo; //...vá para esse próximo...
else //...caso não exista...
break; //...pare
}
if(aux->proximo) { //se existir um próximo elemento...
elem *apagar = aux->proximo; //...salve-o em uma variável para depois apagar...
aux->proximo = aux->proximo->proximo; //..., coloque que o próximo será o elemento seguinte do que vamos apagar...
free(apagar); //...e apague o elemento
}
}
}
void RemoverNoFinal(elem **inicio){
if(*inicio) { //verifica se início não é nulo, ou seja, se a lista não é vazia
if(!(*inicio)->proximo) { //se o primeiro elemento não tiver um próximo...
free(*inicio); //...apague o primeiro e único elemento...
*inicio = NULL; //...e coloque o inicio como NULL...
}
else{ //...caso contrário...
elem *aux = *inicio; //...comece no início...
while (aux->proximo->proximo){ //...e percorra até pegar o penúltimo elemento...
aux = aux->proximo;
}
free(aux->proximo); //...limpe o elemento seguite do penúltimo...
aux->proximo = NULL; //...e defina-o como nulo
}
}
}
void VerLista(elem *inicio){
elem *aux = inicio;
printf("\\n");
for(int i = 1; aux; i++){
printf("%d: %d\\n", i, aux->valor);
aux = aux->proximo;
}
printf("\\n");
}
int main()
{
elem *inicio = NULL; //inicializando o ponteiro
int escolha, num, local;
while(1){
printf("1 - Ver lista\\n2 - Adicionar no inicio\\n3 - Adicionar no meio\\n4 - Adicionar no fim\\n5 - Remover do inicio\\n6 - Remover do meio\\n7 - Remover no final\\n");
scanf("%d", &escolha);
switch (escolha) {
case 1:
VerLista(inicio);
break;
case 2:
scanf("%d", &num);
AdicionarNoInicio(&inicio, num);
break;
case 3:
scanf("%d %d", &num, &local);
AdicionarNoMeio(&inicio, num, local);
break;
case 4:
scanf("%d", &num);
AdicionarNoFinal(&inicio, num);
break;
case 5:
RemoverNoInicio(&inicio);
break;
case 6:
scanf("%d", &local);
RemoverNoMeio(&inicio, local);
break;
case 7:
RemoverNoFinal(&inicio);
break;
default:
printf("Opcao invalida.\\n");
break;
}
}
return 0;
}
Consiste no mesmo conceito de uma lista simplesmente ligada, mas, ao invés dos elementos só serem ligados com o próximo, eles também são ligados com os elementos anteriores. Assim, a struct que usaremos como TAD ficará mais ou menos assim:
typedef struct elem {
//o que está dentro da TAD
struct elem *proximo;
struct elem *anterior;
} elem;
Então, ao invés de fazer apenas uma ligação para cada elemento, basta fazer uma ligação a mais.
Fazendo as devidas mudanças em cada uma das funções, o código completo ficaria assim:
#include <stdio.h>
#include <stdlib.h>
typedef struct elem {
int valor;
struct elem *proximo;
struct elem *anterior;
} elem;
void AdicionarNoInicio(elem **inicio, int value){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
elemento_criado->proximo = *inicio; //atribuindo o ex-primeiro elemento como o próximo
if(*inicio){
elemento_criado->proximo->anterior = elemento_criado; //colocando que o anterior do elemento seguinte é ele mesmo
}
*inicio = elemento_criado; //mudando o início para o elemento que acabamos de criar
}
void AdicionarNoMeio(elem **inicio, int value, int local){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
if(!*inicio){ //verifica se a lista está vazia ao colocar um elemento.
*inicio = elemento_criado;
}
else{
elem* auxiliar = *inicio;
for(int i = 1; i < local-1; i++){ //pegando o elemento anterior ao local onde vamos colocar
if(auxiliar->proximo) //verifica se existe um próximo elemento. Caso não exista, esse é o último elemento
auxiliar = auxiliar->proximo;
else
break;
}
if(auxiliar->proximo){ //se não for o último elemento...
elemento_criado->proximo = auxiliar->proximo;
elemento_criado->anterior = auxiliar;
auxiliar->proximo = elemento_criado;
elemento_criado->proximo->anterior = elemento_criado;
}
else{ //se for o último elemento...
auxiliar->proximo = elemento_criado;
elemento_criado->anterior = auxiliar;
}
}
}
void AdicionarNoFinal(elem **inicio, int value){
elem* elemento_criado = malloc(sizeof(elem)); //criando um novo elemento
elemento_criado->valor = value; //atribuindo o valor que pedimos
if(!*inicio){ //verifica se a lista está vazia ao colocar um elemento.
*inicio = elemento_criado;
}
else{
elem* auxiliar = *inicio;
while(auxiliar->proximo){ //vai percorrendo a lista até achar um elemento que não tem um próximo, ou seja, é o último.
auxiliar = auxiliar->proximo;
}
auxiliar->proximo = elemento_criado;
elemento_criado->anterior = auxiliar;
}
}
void RemoverNoInicio(elem **inicio){
if(*inicio){ //verifica se início não é nulo, ou seja, se a lista não é vazia
elem *aux = *inicio; //salvamos o primeiro elemento para depois limpá-lo da memória
*inicio = (*inicio)->proximo; //pega o segundo elemento da lista
if(*inicio){ //para caso a lista não for ficar vazia
(*inicio)->anterior = NULL;
}
free(aux); //limpa o primeiro elemento da memória para excluí-lo
}
}
void RemoverNoMeio(elem **inicio, int local){
if(*inicio){ //verifica se início não é nulo, ou seja, se a lista não é vazia
elem* aux = *inicio;
for(int i = 1; i < local-1; i++){ //pegando o elemento anterior do elemento que vamos apagar
if(aux->proximo) //se existir um próximo elemento ainda...
aux = aux->proximo; //...vá para esse próximo...
else //...caso não exista...
break; //...pare
}
if(aux->proximo) { //se existir um próximo elemento...
elem *apagar = aux->proximo; //...salve-o em uma variável para depois apagar...
aux->proximo = aux->proximo->proximo; //..., coloque que o próximo será o elemento seguinte do que vamos apagar...
if(aux->proximo){ //se houver um proximo
aux->proximo->anterior = aux;
}
free(apagar); //...e apague o elemento
}
}
}
void RemoverNoFinal(elem **inicio){
if(*inicio) { //verifica se início não é nulo, ou seja, se a lista não é vazia
if(!(*inicio)->proximo) { //se o primeiro elemento não tiver um próximo...
free(*inicio); //...apague o primeiro e único elemento...
*inicio = NULL; //...e coloque o inicio como NULL...
}
else{ //...caso contrário...
elem *aux = *inicio; //...comece no início...
while (aux->proximo->proximo){ //...e percorra até pegar o penúltimo elemento...
aux = aux->proximo;
}
free(aux->proximo); //...limpe o elemento seguite do penúltimo...
aux->proximo = NULL; //...e defina-o como nulo
}
}
}
void VerLista(elem *inicio){
elem *aux = inicio;
printf("\\n");
for(int i = 1; aux; i++){
printf("%d: %d\\n", i, aux->valor);
aux = aux->proximo;
}
printf("\\n");
}
int main()
{
elem *inicio = NULL; //inicializando o ponteiro
int escolha, num, local;
while(1){
printf("1 - Ver lista\\n2 - Adicionar no inicio\\n3 - Adicionar no meio\\n4 - Adicionar no fim\\n5 - Remover do inicio\\n6 - Remover do meio\\n7 - Remover no final\\n");
scanf("%d", &escolha);
switch (escolha) {
case 1:
VerLista(inicio);
break;
case 2:
scanf("%d", &num);
AdicionarNoInicio(&inicio, num);
break;
case 3:
scanf("%d %d", &num, &local);
AdicionarNoMeio(&inicio, num, local);
break;
case 4:
scanf("%d", &num);
AdicionarNoFinal(&inicio, num);
break;
case 5:
RemoverNoInicio(&inicio);
break;
case 6:
scanf("%d", &local);
RemoverNoMeio(&inicio, local);
break;
case 7:
RemoverNoFinal(&inicio);
break;
default:
printf("Opcao invalida.\\n");
break;
}
}
return 0;
}