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

Como já aprendemos a inserir elementos no início e no fim de uma lista, nada mais justo que aprender como retirar nós do início e do fim de uma lista., que é o que iremos aprender neste tutorial de nossa apostila C Progressivo.

No próximo tutorial faremos uma generalização, mostrando como inserir e retirar elementos de qualquer posição da lista, e teremos uma lista completa e flexível.

• Como obter certificação em C
• Download do curso: Apostila C Progressivo

Retirando nós da uma lista em C

Agora vamos aprender como retirar estruturas de uma lista.
Assim como fizemos para inserir, vamos aprender como retirar no início e no fim, que são mais simples e ajudará você a entender melhor.
Depois, quando entender melhor esses conceitos, podemos fazer algo mais completo, que é retirar e inserir uma struct em qualquer posição.

Uma diferença importante é que, quando inseríamos nós, nossas funções eram do tipo void, afinal, simplesmente tínhamos que colocar um nó ali na lista.

Mas quando retiramos, é importante saber que elementos retiramos.
A explicação disso é o bom senso: quando tiramos um elemento de uma lista, é para trabalhar em cima dele, ver seu conteúdo, passar ele para outra função ou extrair algum dado.

Portanto, nossa funções de retirar elementos irão retornar o nó, serão do tipo:

node *retiraInicio(node *LISTA);
node *retiraFim(node *LISTA);

Retirando um nó do início da lista

A primeira coisa que devemos fazer para retirar um nó do início é saber se esse nó realmente existe, ou seja, se a lista não está vazia.

Essa simples verificação é feita usando um teste condicional IF: if(LISTA->prox == NULL)
E caso dê verdadeira, é porque ela está vazia e não há para ser retirado.
Como devemos retornar algo, iremos fazer: return NULL;
Isso é necessário para mostrar que nada foi retirado da lista.

Agora iremos fazer a retirada do primeiro elemento da lista através do uso de um ponteiro para o tipo node, o *tmp
Vamos fazer ele apontar para primeiro elemento da lista: tmp = LISTA->prox;

Então o primeiro elemento da lista está apontado por 'tmp'.
Agora vem a lógica da exclusão de um elemento.
Antes, LISTA->prox aponta para o primeiro elemento, então para excluir esse primeiro elemento, basta fazer com que esse ponteiro aponte para o segundo elemento.
E onde está o segundo elemento? Está em: tmp->prox;

Logo, para excluir o primeiro nó, fazemos: LISTA->prox = tmp->prox
E em seguida retornamos 'tmp', que ainda aponta para aquele nó que foi excluído.
Vale ressaltar que, embora tenhamos tirado ele da lista (fazendo com que ninguém aponte para ele), memória foi alocada para esse nó, então ele ainda existe, e está sendo apontado por 'tmp'.

Como excluir um elemento ao final da lista

Assim como fizemos para tirar uma struct do início, para tirar do fim primeiro temos que checar se a lista está vazia, que é análogo à maneira anteriormente mostrada.

Se notar bem, para retirar um elemento do início da lista, usamos dois ponteiros: LISTA->prox e tmp
Para fazer isso no final da lista, também vamos usar dois ponteiros.
Porém, não vamos poder usar o LISTA->prox pois este está apontado para o início da lista.

Para resolver este problema, iremos usar dois ponteiros neste algoritmo: 'ultimo' e 'penultimo'
Como os próprios nomes podem sugerir, o 'ultimo' aponta para último elemento da lista e o 'penultimo' para o penúltimo elemento da lista.

Nosso objetivo é simples, fazer o ponteiro 'ultimo' chegar ao fim da lista e o 'penultimo' a penúltima posição. Chegando lá, simplesmente fazemos o ponteiro 'penultimo' apontar para NULL, caracterizando este elemento como o último da lista, e retornamos o ponteiro 'ultimo', que contém o elemento retirado.

E como sabemos que um elemento é o último da lista?
Simples, ele aponta para NULL. Então vamos fazer o ponteiro 'ultimo' ir percorrendo a lista até chegar num ponto onde 'ultimo->prox' aponta para NULL, e aí chegamos ao fim.

Porém, antes do 'ultimo' avançar, devemos fazer com que o ponteiro 'penultimo' receba o valor de 'ultimo'. Colocando isso dentro de um laço while, obtemos o que queríamos da seguinte maneira:

while(ultimo->prox != NULL){
 penultimo = ultimo;
 ultimo = ultimo->prox;
}

Agora vamos excluir o último da lista, fazendo o penúltimo elemento apontar para NULL, e retornar ele:
penultimo->prox = NULL;
return ultimo;

Código C da uma Lista encadeada

Logo, o código de um programa em C que implementa uma lista, onde é possível adicionar ou retirar elementos tanto do início como do fim, é:

#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);
node *retiraInicio(node *LISTA);
node *retiraFim(node *LISTA);


int main(void)
{
 node *LISTA = (node *) malloc(sizeof(node));
 if(!LISTA){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
 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. Zerar lista\n");
 printf("2. Exibir lista\n");
 printf("3. Adicionar node no inicio\n");
 printf("4. Adicionar node no final\n");
 printf("5. Retirar do inicio\n");
 printf("6. Retirar do fim\n");
 printf("Opcao: "); scanf("%d", &opt);
 
 return opt;
}

void opcao(node *LISTA, int op)
{
 node *tmp;
 switch(op){
  case 0:
   libera(LISTA);
   break;
   
  case 1:
   libera(LISTA);
   inicia(LISTA);
   break;
  
  case 2:
   exibe(LISTA);
   break;
  
  case 3:
   insereInicio(LISTA);
   break;  
   
  case 4:
   insereFim(LISTA);
   break;
   
  case 5:
   tmp= retiraInicio(LISTA);
   printf("Retirado: %3d\n\n", tmp->num);
   break;
  
  case 6:
   tmp= retiraFim(LISTA);
   printf("Retirado: %3d\n\n", tmp->num);
   break;
  
  default:
   printf("Comando invalido\n\n");
 }
}

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

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


void insereFim(node *LISTA)
{
 node *novo=aloca();
 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=aloca(); 
 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;
  }
 }
}


node *retiraInicio(node *LISTA)
{
 if(LISTA->prox == NULL){
  printf("Lista ja esta vazia\n");
  return NULL;
 }else{
  node *tmp = LISTA->prox;
  LISTA->prox = tmp->prox;
  return tmp;
 }
 
}

node *retiraFim(node *LISTA)
{
 if(LISTA->prox == NULL){
  printf("Lista ja vazia\n\n");
  return NULL;
 }else{
  node *ultimo = LISTA->prox,
    *penultimo = LISTA;
    
    while(ultimo->prox != NULL){
     penultimo = ultimo;
     ultimo = ultimo->prox;
    }
    
    penultimo->prox = NULL;
    return ultimo;  
 }
}

Exercício de C

No próximo tutorial de nosso curso de C, vamos ensinar como inserir e retirar elementos de qualquer posição de uma lista, finalizando complemente nossa implementação de uma lista em C.
Tente fazer essas implementações, que serão explicadas no próximo tutorial de nosso curso de C.

Como criar uma lista completa em C