Lista simplesmente encadeada com cabeça em C: Inserindo nós no início e no fim

Agora que já vimos como funciona uma lista em C, vamos aprender como implementar, como programar uma lista desde o início.

Como há diversas maneiras de se fazer isso, pois há diversos tipos de listas, vamos fazer vários tipos de listas e, aos poucos, iremos mostrar as ideias que podemos utilizar para criar mais recursos para nossas listas.

• Baixe o conteúdo do site: Apostila de C

Obtenha sua certificação de programação C para entrar no Mercado de Trabalho!

Tipos de Listas em C

No esquema que mostramos no tutorial passado de nossa apostila de C, explicamos como funciona uma lista, como seria adicionar um elemento (nó) em seu início, no seu fim ou em qualquer posição da lista.

Também vimos como retirar um elemento da lista, tanto do início, do fim como de uma posição intermediária.
Só aí já iriam várias implementações destas ideias.

E além destes recursos, há os vários tipos de listas.
Vamos estudar as simplesmente encadeadas, ou seja, seus nós são structs que possuem só um ponteiro, que aponta sempre para o elemento seguinte da lista.

Além deste tipo, que é o mais simples, há ainda as listas duplamente encadeadas, que possuem ponteiros para o próximo e para o nó anterior.
Há também as listas circulares, onde o último elemento se liga ao primeiro, e por aí vai.

Lista encadeada com cabeça

Neste artigo iremos focar nas simplesmente encadeadas, e sobre como inserir nós no início e ao fim da lista.
Embora sejam 'poucas' coisas, você verá que na verdade, na hora de implementar pela primeira vez, pode parecer algo bem difícil e confuso.

Mas iremos progredir aos poucos. Depois iremos aprender como excluir os elementos do fim, do início, bem como inserir ou retirar de qualquer local da lista, e até mesmo buscar nós específicos.
Mas sem pressa, por hora, vamos fazer o básico, que só isso já vai dar mais de 150 linhas de código.

Podemos implementar uma lista simplesmente encada de duas maneiras: com cabeça e sem cabeça.
Onde a cabeça de uma lista seria um nó, que foi declarado explicitamente no início do programa.
Não usaremos, na verdade, o conteúdo deste nó, também chamado de célula ou cabeça, pois como veremos, ele não será relevante.
Ele serve para sinalizar o início da lista, para sabermos que ela inicia ali, naquele endereço fixo de memória.

Fazemos isso na primeira linha de nossa main():
node *LISTA = (node *) malloc(sizeof(node));

Como explicamos no tutorial passado, esse 'node' é um tipo que definimos (typedef struct), uma estrutura que armazena um número inteiro e um ponteiro para o tipo 'node' (nó, em inglês).

A lista, de fato, será colocada no ponteiro deste nó inicial (cabeça), que está em: LISTA->prox
Como acabamos de criar a lista, esse ponteiro deverá apontar para NULL, para sinalizar que a lista está vazia.
Vamos fazer isso através do método 'inicia()', que simplesmente faz: LISTA->prox = NULL;

Criamos um método para isto, pois este simples ato faz nossa lista ser zerada, sendo possível ser preenchida de novo.

Em seguida, invocamos o método menu(), que irá mostrar ao usuário uma série de opções e irá armazenar a opção escolhida, que será enviada ao método 'opcao()', que irá tratar a opção escolhida através de um teste condicional SWITCH.

Como inserir um nó no início da lista

Inserir nós no início da lista é bem simples de se fazer, pois temos um head node, ou seja, um nó cabeça, que nos indica onde está o início de nossa lista: LISTA->prox

Primeiro precisamos criar o nosso novo nó, o 'novo'.
Agora devemos fazer dois passos: primeiros fazemos LISTA->prox apontar para nosso novo nó, depois fazemos nosso nó apontar para o próximo elemento da lista.

Mas aqui temos um problema.
Antes o 'LISTA->prox' apontava para um local de memória que tinha o próximo nó.
Mas quando apontamos ele para o nó 'novo', perdemos essa referência.

Vamos resolver isso criando um ponteiro para armazenar o local que está 'LISTA->prox' antes de inserirmos o novo nó.
Vamos chamar de 'oldHead', pois era a cabeça antiga da lista:
node *oldHead = LISTA->prox;

Então, agora apontamos a cabeça da lista para nosso novo nó: LISTA->prox = novo;
E apontamos nosso novo nó para o nó antigo: novo->prox = oldHead;

E pronto, inserimos uma estrutura no início da lista. Interessante, não?

Como inserir um nó ao final da lista

Vamos agora inserir um nó ao final da lista.
Antes de mais nada, devemos alocar memória para este nó e preencher o número que iremos armazenar nele, o que é facilmente feito através da função malloc(), conforme estudamos na seção de nosso curso de Alocação Dinâmica de Memória:
node *novo=(node *) malloc(sizeof(node));

Lembrando sempre de checar se a memória foi alocada (caso não, devemos dar um exit() no programa, informando o erro).
Agora devemos procurar o final da lista.

Antes, devemos checar se ela está vazia, através do método vazia(), que simplesmente checa o elemento: LISTA->prox
Se este apontar para NULL, a lista está vazia, afinal, esse elemento é a cabeça da lista, aponta par ao início dela.
Caso seja realmente vazia, vamos fazer com que a cabeça aponte para este novo nó que criamos, o 'novo':
LISTA->prox = novo;

Agora, este nó será o último elemento da lista, então ele DEVE apontar para NULL:
novo->prox = NULL;

E caso não seja uma lista vazia? Bem, devemos procurar o final da lista, que é um nó que aponta para NULL.
Para isso, vamos declarar um ponteiro de nó:
node *tmp;

A ideia é fazer esse ponteiro apontar para todos os elementos da lista e checar se ele é o último.
Algo como "Hey, você é o último da lista? Não? Próximo! E você, é? Não? Ok, próximo..."

Então posicionamos ele apontando para o início da lista, nossa cabeça: tmp = LISTA->prox
Agora vamos percorrer todos os nós, e só vamos parar quando o nó apontar para NULL, ou seja, só vamos parar quando a seguinte comparação retornar valor lógico TRUE:
tmp->prox == NULL

Se retornar falso, devemos avançar a lista, e isso é feito da seguinte maneira:
tmp = tmp->prox;

Isso é feito com um laço while, que sai varrendo todos os nós e só para quando encontra o último:
while(tmp->prox != NULL)
   tmp = tmp->prox;

Ou seja, nosso ponteiro agora aponta para o próximo elemento da lista.
E quando achar o ponteiro que aponta para NULL? Aí colocamos aquele nó que criamos, o 'novo'.
Ou seja, em vez do último nó apontar para NULL, vai apontar para novo:
tmp->prox = novo;

E como, ao declarar o 'novo', fizemos ele apontar para NULL, identificamos ele como o último elemento da lista.
Genial, não?

Como exibir os elementos de uma lista

Bom, em nada adianta alocar os elementos no início ou fim da lista, se não pudermos ver essa lista crescendo diante de nossos olhos.
Por isso vamos criar uma função que será responsável por exibir todos os elementos da lista, do início ao fim.

E onde é o início da lista? Ué, no nó cabeça: LISTA->prox
E onde é o final? É em um nó que aponta para NULL.

Mais uma vez precisamos criar um ponteiro que vai apontar para cada um dos elementos da lista, e depois imprimir o número armazenado na estrutura.

Vamos chamar, novamente, esse nó temporário de 'tmp' e deve apontar, inicialmente para a cabeça da lista:
node *tmp = LISTA->prox;

Agora vamos imprimir o primeiro elemento (caso exista, senão existir, dizemos que a lista está vazia).
Estamos em um nó, então imprimimos ele e avançamos.
Para imprimir, damos um print no inteiro: tmp->num
E para avançar na lista: tmp = tmp->prox

E quando devemos parar o avanço? Quando chegarmos ao fim da lista. E quando isso ocorre? Quando nosso ponteiro temporário apontar para NULL. Logo, isso é feito dentro de um laço while:
while( tmp != NULL)

Pronto, membros da lista exibidos.

Liberando a memória armazenada para uma lista

Como enfatizamos bem ao ensinar o uso da função free() para liberar a memória, sempre devemos devolver o que foi alocado para nosso sistema, sob risco de ocorrer vazamento de memória que podem atrapalhar e travar um computador.

Na lista, as coisas são um pouco mais complexas, pois alocamos memória várias vezes!
Portanto, devemos sair desalocando e liberando cada nó que alocamos!

Bom, vamos lá, mais uma vez usar nosso ponteiro para nó (caso não seja uma lista vazia), apontar para cada estrutura da lista e dar um free() nela. Vamos chamar esse ponteiro para nó de 'atual'.
Inicialmente aponta para a cabeça: node *atual = LISTA->prox;
Agora libera a memória: free(atual);
Indo para o próximo elemento: atual = atual->prox;
Ok?

Não, isso está errado. Lembre-se que se liberamos o primeiro nó e junto com ele o seu ponteiro *prox.
Ou seja, não temos mais o local do próximo nó. E agora, José?

A solução é, antes de liberar um nó, salvar seu ponteiro que está apontando para o próximo nó.
Vamos criar um ponteiro para nó para guardar essa informação, será o 'proxNode'.

Vamos começar de novo, agora salvando o próximo nó antes de desalocá-lo.
Recebe o primeiro nó: atual = LISTA->prox;
Guarda o endereço do próximo nó: proxNode = atual->prox;
Desaloca: free(atual);

Pronto. Desalocamos o nó, e sabemos onde está o próximo (guardado no ponteiro 'proxNode').
Agora esse nó será o próximo a ser desalocado, basta repetir o procedimento:
Recebe o próximo nó: atual = proxNode;
Guarda o endereço do próximo nó: proxNode = atual->prox;
Desaloca: free(atual);

E assim sucessivamente. E quando isso deve parar? Quando chegar ao final.
E onde é o final da lista? É no nó que aponta para NULL.

Ou seja, vamos avançando na lista, e quando estivermos em um nó que é NULL, paramos, não tentamos desalocá-lo.
Assim, só liberamos memória quando o nó atual não for NULL: while(atual != NULL), e dentro desse while vão aqueles procedimentos que falamos (guarda o endereço do próximo, desaloca e vai para o próximo).

Código em C de uma lista encadeada

#include <stdio.h>
#include <stdlib.h>

struct Node{
 int num;
 struct Node *prox;
}; 
typedef struct Node node;

void inicia(node *LISTA);
int menu(void);
void opcao(node *LISTA, int op);
node *criaNo();
void insereFim(node *LISTA);
void insereInicio(node *LISTA);
void exibe(node *LISTA);
void libera(node *LISTA);


int main(void)
{
 node *LISTA = (node *) malloc(sizeof(node));
 if(!LISTA){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }
 inicia(LISTA);
 int opt;
 
 do{
  opt=menu();
  opcao(LISTA,opt);
 }while(opt);

 free(LISTA);
 return 0;
}

void inicia(node *LISTA)
{
 LISTA->prox = NULL;
}

int menu(void)
{
 int opt;
 
 printf("Escolha a opcao\n");
 printf("0. Sair\n");
 printf("1. Exibir lista\n");
 printf("2. Adicionar node no inicio\n");
 printf("3. Adicionar node no final\n");
 printf("4. Zerar lista\n");
 printf("Opcao: "); scanf("%d", &opt);
 
 return opt;
}

void opcao(node *LISTA, int op)
{
 switch(op){
  case 0:
   libera(LISTA);
   break;
   
  case 1:
   exibe(LISTA);
   break;
  
  case 2:
   insereInicio(LISTA);
   break;
  
  case 3:
   insereFim(LISTA);
   break;  
   
  case 4:
   inicia(LISTA);
   break;
  
  default:
   printf("Comando invalido\n\n");
 }
}

int vazia(node *LISTA)
{
 if(LISTA->prox == NULL)
  return 1;
 else
  return 0;
}


void insereFim(node *LISTA)
{
 node *novo=(node *) malloc(sizeof(node));
 if(!novo){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }
 printf("Novo elemento: "); scanf("%d", &novo->num);
 novo->prox = NULL;
 
 if(vazia(LISTA))
  LISTA->prox=novo;
 else{
  node *tmp = LISTA->prox;
  
  while(tmp->prox != NULL)
   tmp = tmp->prox;
  
  tmp->prox = novo;
 }
}

void insereInicio(node *LISTA)
{
 node *novo=(node *) malloc(sizeof(node));
 if(!novo){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }
 printf("Novo elemento: "); scanf("%d", &novo->num);
 
 node *oldHead = LISTA->prox;
 
 LISTA->prox = novo;
 novo->prox = oldHead;
}

void exibe(node *LISTA)
{
 if(vazia(LISTA)){
  printf("Lista vazia!\n\n");
  return ;
 }
 
 node *tmp;
 tmp = LISTA->prox;
 
 while( tmp != NULL){
  printf("%5d", tmp->num);
  tmp = tmp->prox;
 }
 printf("\n\n");
}

void libera(node *LISTA)
{
 if(!vazia(LISTA)){
  node *proxNode,
     *atual;
  
  atual = LISTA->prox;
  while(atual != NULL){
   proxNode = atual->prox;
   free(atual);
   atual = proxNode;
  }
 }
}

Considerações sobre listas em C

Sim, não é fácil.
Ponteiros não são fáceis, alocação também não é, e obviamente se juntarmos os dois, vai dar algo que realmente não é simples. Porém, não é impossível.

É perfeitamente natural não entender de primeira.
Leia, releia, veja mais uma vez. Clareie a mente, depois volte a estudar de novo.
Tente realmente entender cada passo, tente refazer. Pesquise na internet, leia o livro que indicamos.
Vai levar um tempo até se habituar com essas ideias, mas acredite, acontece com todos.

Essas ideias são EXTREMAMENTE poderosas!
Note que estamos tratando de estruturas, e essas structs podem ser qualquer coisa.
Podem guardar dados de funcionários de uma empresa, informações de aluno de uma escola ou cada uma pode ser a bula de um remédio de uma farmácia, no sistema.

Se tivermos 10 funcionários, as listas alocam espaço somente para estes 10.
Se forem 100 alunos, teremos espaço para exatos 100 alunos. E se a farmácia tiver mil tipos de remédios, só vamos usar mil espaços de struct. Nem mais, nem menos.
Precisa guardar mais uma informação? Somente mais uma struct será usada.

E como veremos no próximo tutorial, quando não precisarmos de mais um elemento da lista, liberaremos seu espaço de memória.
Resumindo: é um algoritmo extremamente eficiente, consome o mínimo de memória possível, e acredite: esta ideia está sendo usada agora, em seu sistema operacional.

Não desanime, continue estudando.

Exercícios sobre listas

No próximo tutorial sobre listas de nossa apostila de C, iremos ensinar como retirar um elemento do início, um elemento do fim e um intermediário.
Tente implementar estes recursos.

Após tentar, estude aqui Como retirar estruturas do início e final de uma lista em C .