11
Obrigado

Algumas palavras de agradecimento nunca são demais.

Listas simplesmente encadeadas

Listas encadeadas em C são estruturas de dados que encadeiam os elementos através de um ponteiro. Elas também possuem uma estrutura dinâmica, ou seja, não precisamos conhecer com antecedência o número de elementos que ela conterá. Nas listas encadeadas, todos os elementos, exceto o último, apontam para o seguinte. Assim, cada elemento é formado por dois componentes: o dado armazenado e a ligação com o elemento seguinte. As listas encadeadas podem ser utilizadas para realizar diversas operações de inserção e eliminação de elementos.




Requisitos

Os requisitos das listas simplesmente encadeadas são os seguintes: os tipos de dados, as estruturas, o uso do typedef, os ponteiros e as funções usuário. Como dito anteriormente, cada elemento da lista está ligado ao seguinte:



Enquanto em uma tabela os elementos estão em sequência na memória, nas listas os elementos estão dispersos e, na memória, a representação deles é aleatória em função do espaço alocado.

O ponteiro seguinte do último elemento deve apontar para NULL (fim da lista). Para acessar um elemento, a lista é varrida desde o início. O ponteiro seguinte permite o deslocamento para o elemento seguinte.

Esse deslocamento ocorre em um único sentido, do primeiro ao último elemento. Se você quiser se deslocar nos dois sentidos, será necessário utilizar uma lista duplamente encadeada.

Construção do modelo de um elemento da lista

Para determinar um elemento da lista, vamos usar o tipo struct. O elemento da lista conterá um campo dado e um ponteiro seguinte. O ponteiro seguinte deve ser do mesmo tipo que o elemento, senão ele não poderá apontar para o elemento. O ponteiro seguinte permitirá o acesso ao próximo elemento.

typedef struct ElementoLista {
char *dado;
struct ElementoLista *seguinte;
}Elemento;


Para controlar a lista, o melhor é salvar certos elementos: o primeiro elemento, o último elemento e o número de elementos. Para tanto, outra estrutura será utilizada. Esse procedimento não é obrigatório, já que você pode utilizar variáveis.

typedef struct ListaDetectada {   
  elemento *início;   
  elemento *fim;   
  int tamanho;   
}Lista;   


O ponteiro início possui o endereço do primeiro elemento da lista e o ponteiro fim, o endereço do último elemento da lista. A variável tamanho integra o número de elementos.

Seja qual for a posição na lista, os ponteiros início e fim sempre apontarão, respectivamente, para o primeiro e o último elemento. O campo tamanho conterá o número de elementos da lista, seja qual for a operação efetuada na lista.

Operações em listas encadeadas

Para inserção e exclusão de elementos, uma única função é suficiente se ela for desenvolvida corretamente, de acordo com as necessidades. No entanto, lembre-se que esse artigo é puramente didático. É por isso que foi criada uma função para cada operação de inserção e exclusão.

Inicialização

Modelo da função:
void inicialização (Lista *lista);


A operação deve ser executada antes de qualquer outra operação da lista. Ela posiciona os ponteiros início e fim no valor NULL e o tamanho no valor 0.

Função:
void inicialização (Lista *lista){   
  lista->início = NULL;   
  lista->fim = NULL;   
  tamanho = 0;   
}   


Observação: com o operador ->, a linguagem C/C++ nos garante uma maneira mais simples de escrever o acesso a um atributo através de um ponteiro. Na função anterior, acessamos o atributo início através do ponteiro lista.

Inserção de elemento da lista

A seguir, indicamos as etapas do algoritmo de inserção e o registro dos elementos:
  • Declaração dos elementos a ser inseridos;
  • Alocação da memória para o novo elemento;
  • Preenchimento do conteúdo do campo de dados;
  • Atualização dos ponteiros do primeiro e último elemento, se necessário.


Em listas com apenas um elemento, o primeiro e o último elementos são o mesmo. A seguir, descrevemos as diferentes formas de inserção para atualizar o tamanho da lista e adicionar um novo elemento.

Inserção em lista vazia

Modelo da função:
int ins_em_lista_vazia (Lista *lista, char *dado);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, o ponteiro seguinte ao novo elemento aponta para NULL, ponteiros início e fim apontam para o novo elemento e o tamanho da lista é atualizado.

Função:
/* inserção em lista vazia */   
int ins_em_lista_vazia (Lista * lista, char *dado){   
  elemento *novo_elemento;   
  if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)   
    return -1;   
  if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))   
      == NULL)   
    return -1;   
  strcpy (novo_elemento->dado, dado);   

  novo_elemento->seguinte = NULL;   
  lista->início = novo_elemento;   
  lista->fim = novo_elemento;   
  lista->tamanho++;   
  return 0;   
}   

Inserção no início da lista

Modelo da função:
int ins_início_lista (Lista *lista,char *dado);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, o ponteiro seguinte ao novo elemento aponta para NULL, ponteiro início aponta para o novo elemento, ponteiro fim não muda e o tamanho da lista aumenta em uma unidade.

Função:
/* inserção no início da lista */   
int ins_início_lista (Lista * lista, char *dado){   
  elemento *novo_elemento;   
  if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)   
    return -1;   
  if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))   
      == NULL)   
    return -1;   
  strcpy (novo_elemento->dado, dado);   

  novo_elemento->seguinte = lista->início;   
  lista->início = novo_elemento;   
  lista->tamanho++;   
  return 0;   
}   

Inserção no fim da lista

Modelo da função:
int ins_fim_lista (Lista *lista, elemento *atual, char *dado);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, o ponteiro seguinte ao último elemento aponta para o novo elemento, ponteiro fim aponta para o novo elemento, ponteiro início não muda e o tamanho da lista aumenta em uma unidade.



Função:
/*inserção no fim da lista */   
int ins_fim_lista (Lista * lista, elemento * atual, char *dado){   
  elemento *novo_elemento;   
  if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)   
    return -1;   
  if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))   
      == NULL)   
    return -1;   
  strcpy (novo_elemento->dado, dado);   
  atual->seguinte = novo_elemento;   
  novo_elemento->seguinte = NULL;   
  lista->fim = novo_elemento;   
  lista->tamanho++;   
  return 0;   
}   

Inserção em outro ponto da lista

Modelo da função:
int ins_lista (Lista *lista, char *dado,int pos);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

A inserção será feita depois de uma certa posição ser transformada em argumento na função. A posição indicada não deve ser o último elemento. Nesse caso, é preciso utilizar a função de inserção no fim da lista.

Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, escolher uma posição na lista (inserção será feita depois da posição escolhida), ponteiro seguinte ao novo elemento indica o endereço do ponteiro seguinte do elemento atual, ponteiro seguinte ao elemento atual aponta para o novo elemento, ponteiros início e fim não mudam, o tamanho aumenta em uma unidade.



Função:
/* inserção na posição solicitada */   
int ins_lista (Lista * lista, char *dado, int pos){   
  if (lista->tamanho < 2)   
    return -1;   
  if (pos < 1 || pos >= lista->tamanho)   
    return -1;   
  elemento *atual;   
  elemento *novo_elemento;   
  int i;   
  if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)   
    return -1;   
  if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))   
      == NULL)   
    return -1;   
  atual = lista->início;   
  for (i = 1; i < pos; ++i)   
    atual = atual->seguinte;   
  if (atual->seguinte == NULL)   
    return -1;   
  strcpy (novo_elemento->dado, dado);   
  novo_elemento->seguinte = atual->seguinte;   
  atual->seguinte = novo_elemento;   
  lista->tamanho++;   
  return 0;   
}   

Remoção de um elemento da lista

Veja o algoritmo de remoção de um elemento da lista: uso de ponteiro temporário para salvar o endereço dos elementos a ser removidos, o elemento a ser removido fica depois do elemento atual, o ponteiro seguinte ao elemento atual aponta para o endereço do ponteiro seguinte ao elemento a ser removido, liberar a memória ocupada pelo elemento removido e atualizar o tamanho da lista.

Remoção no início da lista

Modelo da função:
int remov_início (Lista *lista);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

Etapas: ponteiro remov_elem conterá o endereço do primeiro elemento, ponteiro início exibirá o segundo elemento e o tamanho da lista perde uma unidade.

Função:
 /*Remoção no início da lista */   
int remov_início (Lista * lista){   
  if (lista->tamanho == 0)   
    return -1;   
  elemento *remov_elemento;   
  remov_elemento = lista->início;   
  lista->início = lista->início->seguinte;   
  if (lista->tamanho == 1)   
    lista->fim = NULL;   
  free (remov_elemento->dado);   
  free (remov_elemento);   
  lista->tamanho--;   
  return 0;   
}   

Remoção em outro ponto da lista

Modelo da função:
int remov_na_lista (Lista *lista, int pos);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

Etapas: ponteiro remov_elem conterá o endereço para o qual aponta o ponteiro seguinte do elemento atual, o ponteiro seguinte do elemento atual apontará para o elemento para o qual aponta o ponteiro seguinte ao elemento depois do elemento atual. Se o elemento atual for o penúltimo elemento, o ponteiro fim deve ser atualizado. O tamanho da lista perde uma unidade

Função:
/* remover elemento após a posição solicitada */   
int remov_na_lista (Lista * lista, int pos){   
  if (lista->tamanho <= 1 || pos < 1 || pos >= lista->tamanho)   
    return -1;   
  int i;   
  elemento *atual;   
  elemento *remov_elemento;   
  atual = lista->início;   

  for (i = 1; i < pos; ++i)   
    atual = atual->seguinte;   
  remov_elemento = atual->seguinte;   
  atual->seguinte = atual->seguinte->seguinte;   
  if(atual->seguinte == NULL)   
          lista->fim = atual;   
  free (remov_elemento->dado);   
  free (remov_elemento);   
  lista->tamanho--;   
  return 0;   
}   

Exibição da lista

Para exibir a lista inteira, podemos nos posicionar no início da lista (através do ponteiro início). Depois, utilizando o ponteiro seguinte de cada elemento, a lista será exibida do primeiro ao último elemento. A condição de parada é fornecida pelo ponteiro seguinte ao último elemento, cujo valor é NULL.

Função:
/* exibição da lista */   
void exibir (Lista * lista){   
  elemento *atual;   
  atual = lista->início;   
  while (atual != NULL){   
      printf ("%p - %s\n", atual, atual->dado);   
      atual = atual->seguinte;   
  }   
}   

Destruição da lista

Para destruir a lista inteira, utilizaremos o recurso de remoção no início da lista uma vez que o tamanho da lista for maior que zero.

Função:
/* destruir a lista */   
void destruir (Lista * lista){   
  while (lista->tamanho > 0)   
    remov_início (lista);   
}   

Exemplo completo

lista.h

/* ---------- lista.h ----------- */   
typedef struct ElementoLista   
{   
  char *dado;   
  struct ElementoLista *seguinte;   
} elemento;   
typedef struct ListaDetectada   
{   
  elemento *início;   
  elemento *fim;   
  int tamanho;   
} Lista;   

/* inicialização da lista */   
void inicialização (Lista * lista);   

/* INSERÇÃO */   

/*inserção em lista vazia */   
int ins_em_lista_vazia (Lista * lista, char *dado);   

/* inserção no início da lista */   
int ins_início_lista (Lista * lista char *dado);   

/* inserção no fim da lista */   
int ins_fim_lista (Lista * lista, elemento * atual, char *dado);   

/* Inserção em outro lugar */   
int ins_lista (Lista * lista, char *dado, int pos);   

/* REMOÇÃO */   

int remov_início (Lista * lista);   
int remov_na_lista (Lista * lista, int pos);   

int menu (Lista *lista,int *k);   
void exibir (Lista * lista);   
void destruir (Lista * lista);   
/* -------- FIM lista.h --------- */   

lista_function.h

/* ---------- function.h ----------- */
void   inicialização (Lista * lista)   {     
lista->início = NULL;     
lista->fim = NULL;     
lista->tamanho = 0;   
}

/*inserção em lista vazia*/
int ins_em_lista_vazia (Lista * lista, char *dado){     
elemento *novo_elemento;     
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;     
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))         == NULL)
return -1;     
strcpy (novo_elemento->dado, dado);     
novo_elemento->seguinte = NULL;     
lista->início = novo_elemento;     
lista->fim = novo_elemento;     
lista->tamanho++;     
return 0;   
}

/* inserção no início da  lista */   
int ins_início_lista (Lista * lista, char *dado){     
elemento *novo_elemento;     
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;     
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))         == NULL)
return -1;     
strcpy (novo_elemento->dado, dado);     
novo_elemento->seguinte = lista->início;     
lista->início = novo_elemento;     
lista->tamanho++;     
return 0;   
}

/*inserção no fim da lista */   
int ins_fim_lista (Lista * lista, elemento * atual, char *dado){     
elemento *novo_elemento;     
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)       
return -1;     
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))         == NULL)
return -1;     
strcpy (novo_elemento->dado, dado);     
atual->seguinte = novo_elemento;     
novo_elemento->seguinte = NULL;     
lista->fim = novo_elemento;     
lista->tamanho++;     
return 0;   
}

/* inserção na posição solicitada */   
int ins_lista (Lista * lista, char *dado, int pos){     
if (lista->tamanho < 2)       
return -1;     
if (pos < 1 || pos >= lista->tamanho)       
return -1;     
elemento *atual;     
elemento *novo_elemento;     
int i;     
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)       
return -1;     
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))         == NULL)
return -1;     
atual = lista->início;     
for (i = 1; i < pos; ++i)       
atual= atual->seguinte;     
if (atual->seguinte == NULL)       
return -1;     
strcpy (novo_elemento->dado, dado);     
novo_elemento->seguinte = atual->seguinte;     
atual->seguinte = novo_elemento;     
lista->tamanho++;     
return 0;   
}

/*Remoção no início da lista */   
int remov_início (Lista * lista){     
if (lista->tamanho == 0)       
return -1;     
elemento *remov_elemento;     
remov_elemento = lista->início;     
lista->início = lista->início->seguinte;     
if (lista->tamanho == 1)       
lista->fim = NULL;     
free (remov_elemento->dado);     
free (remov_elemento);     
lista->tamanho--;     
return 0;   
}

/* Remoção de elemento depois da posição solicitada */   
int remov_na_lista (Lista * lista, int pos){     
if (lista->tamanho <= 1 || pos < 1 || pos >= lista->tamanho)       
return -1;     
int i;     
elemento *atual;     
elemento *remov_elemento;     
atual = lista->início;     
for (i = 1; i < pos; ++i)       
atual = atual->seguinte;     
remov_elemento = atual->seguinte;     
atual->seguinte = atual->seguinte->seguinte;     
if(atual->seguinte == NULL)             lista->fim = atual;     
free (remov_elemento->dado);     
free (remov_elemento);     
lista->tamanho--;     
return 0;   
}   

/* Exibição da lista */   
void exibe (Lista * lista)
{     
elemento *atual;     
atual = lista->início;     
while (atual != NULL){         
printf ("%p - %s\n", atual, atual->dado);         
atual = atual->seguinte;     
}   
}   

/*Destruir lista */   
void destruir (Lista * lista){     
while (lista->tamanho > 0)       
remov_ início (lista);   }   
int menu (Lista *lista,int *k){     
int selecionar;     
printf("********** MENU **********\n");     
if (lista->tamanho == 0){       
printf ("1. Adição do 1° elemento\n");       
printf ("2. Fechar\n");     
}else if(lista->tamanho == 1 || *k == 1){       
printf ("1. Inserção no início da lista\n");       
printf ("2. Inserção no fim da lista\n");       
printf ("4. Remoção no início da lista\n");       
printf ("6. Destruir a lista\n");       
printf ("7. Fechar\n");     }
else {       
printf ("1. Inserção no início da lista\n");       
printf ("2. Inserção no fim da lista\n");       
printf ("3. Inserção após a posição especificada\n");       
printf ("4. Remoção no início da lista\n");       
printf ("5. Remoção após a posição especificada\n");       
printf ("6. Destruir a lista\n");       
printf ("7. Fechar\n");     }     
printf ("\n\n Selecionar: ");     
scanf ("%d", &selecionar);     
getchar();     
if(lista->tamanho == 0 && selecionar == 2)       selecionar = 7;     
return selecionar;   
}   

/* -------- FIM lista_function.h --------- */   

lista.c

/* ---------- lista.c ----------- */
#include <stdio.h>
#include <stdlib.h>   
#include <string.h>   
#include "lista.h"   
#include "lista_function.h"   

int main (void)   {     
char selecionar;     
char *nome;     
Lista *lista;     
elemento *atual;     
if ((lista = (Lista *) malloc (sizeof (Lista))) == NULL)       
return -1;     
if ((nome = (char *) malloc (50)) == NULL)       
return -1;     
atual = NULL;     
selecionar = 'o';     
inicialização (lista);     
int pos, k;     
while (selecionar != 7){         
selecionar = menu (lista, &k);         
switch (selecionar){           
case 1:          
printf ("Inserir um elemento: ");             
scanf ("%s", nome);             
getchar ();             
if (lista->tamanho == 0)               
ins_em_lista_vazia (lista, nome);             
else               ins_início_lista (lista, nome);             
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho,                     lista->início->dado, lista->fim->dado);             
exibe (lista);             
break;           
case 2:             
printf ("Inserir um elemento:");             
scanf ("%s", nome);             
getchar ();             
ins_fim_lista (lista, lista->fim, nome);             
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho,                     lista->início->dado, lista->fim->dado);             
exibe (lista);             
break;           
case 3:             
printf ("Inserir um elemento:");             
scanf ("%s", nome);             
getchar ();             
do{                 printf ("Inserir a posição:");                 
scanf ("%d", &pos);        }             
while (pos < 1 || pos > lista->tamanho);             
getchar ();             
if (lista->tamanho == 1 || pos == lista->tamanho){                 
k = 1;                 
printf("-----------------------------------------------\n");                 
printf("/!\\A inserção falhou. Utilize o menu {1|2} /!\\\n");                 
printf("-----------------------------------------------\n");                 
break;        }             
ins_lista (lista, nome, pos);             
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho,                     
lista->início->dado, lista->fim->dado);             
exibe (lista);             
break;           
case 4:             
remov_início (lista);             
if (lista->tamanho != 0)               printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho,                       lista->início->dado, lista->fim->dado);             
else               printf ("lista vazia\n");             
exibir (lista);             
break;           
case 5:             
do{                 printf ("Inserir a posição: ");                 
scanf ("%d", &pos);        }             
while (pos < 1 || pos > lista->tamanho);             
getchar ();             
remov_na_lista (lista, pos);             
if (lista->tamanho != 0)               
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho,                       lista->início->dado, lista->fim->dado);             
else               printf ("lista vazia\n");             
exibir (lista);             
break;           
case 6:             
destruir (lista);             
printf ("A lista foi destruída: %d elementos\n", lista->tamanho); break; } 
} 
return 0;
}
/* -------- FIM lista.c --------- */ 


Foto: © Everypixel.
Veja também
Este documento, intitulado 'Listas simplesmente encadeadas', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.

Assine nossa newsletter!

Receba toda semana o melhor conteúdo

Assine nossa newsletter!