Como criar uma lista encadeada com cabeça em C ? ✅
Resumo
Já pensou como uma estrutura de dados funciona por baixo dos panos? Não? Então, é isso que vamos ver hoje!
Primeiramente, a lista encadeada com cabeça é uma estrutura de dados onde os seus nós/itens estão interligados da seguinte maneira:
[Nó cabeça] -> [1º elemento] -> [2º elemento] -> [3º elemento] -> NULL
O nó cabeça é o item inicial da lista e serve apenas para facilitar o desenvolvimento dessa estrutura de dados. Por isso, temos que ter em mente que uma lista sem elementos na verdade possui apenas o nó cabeça e mais nada.
Lembrando que um nó contém no mínimo os seguintes atributos:
valor: de qualquer tipo
ponteiro: que aponta para o próximo nó
Implementação do zero.
1 - Criar arquivos
- Primeiro crie os arquivos TadLista.h, TadLista.c e main.c
- O arquivo TadLista.h (TAD = Tipo abstrato de dados) serve para definir as funções que a nossa lista terá.
- O arquivo TadLista.c é a implementação das funções definidas no arquivo TadLista.h.
- Por fim, o arquivo main.c servirá para executarmos a nossa lista.
2 - Conteúdo do arquivo TadLista.h
Considerando que uma lista básica tem as funcionalidades de inserção, deleção e busca, o arquivo TadLista.h terá esse conteúdo:
(A lista terá nós com conteúdo do tipo inteiro)
// ** Conteúdo do arquivo TadLista.h **
typedef struct noh Noh;
// Métodos primitivos de uma lista
Noh *criar();
Noh *inserir(Noh *cabeca, int valor);
int remover(Noh *cabeca, int valor);
// Métodos não primitivos de uma lista
void imprimir(Noh *cabeca);
3 - Conteúdo do arquivo TadLista.c
Agora começa a parte mais legal! 😁
Dentro arquivo TadLista.c, vamos iniciar a implementação dessas funcionalidades da lista.
- Começando com a definição do nó da lista
#include <stdio.h>
#include <stdlib.h>
#include "TadLista.h"
typedef struct noh {
int conteudo;
Noh *proximo;
} Noh;
- Em seguida a implementação da função de criação
Noh *criar() {
Noh *cabeca;
// Alocar espaço no Heap (Memória principal) para o nó cabeça
cabeca = (Noh *) malloc(sizeof(Noh));
// Uma lista vazia tem o nó cabeça apontando para NULL
cabeca->proximo = NULL;
return cabeca;
}
- Implementação da função de inserção
Noh *inserir(Noh *cabeca, int valor) {
// Criação de um novo nó para ser inserido na lista
Noh *novo;
novo = (Noh *) malloc(sizeof(Noh));
novo->conteudo = valor;
novo->proximo = cabeca->proximo;
/*
Considerando que isto é uma lista vazia: [Nó cabeça]-> NULL
Para inserirmos um elemento 15 dentro dessa lista, precisamos fazer o
nó cabeça apontar para esse novo elemento sem quebrar toda a estrutura.
Assim, após a inserção elemento 15, a lista ficará assim:
[Nó cabeça]->[15]->NULL
Se continuarmos inserindo o valor 8 por exemplo, teremos o seguinte:
[Nó cabeça]->[8]->[15]->NULL
Ou seja, o novo elemento a ser adicionado sempre ficará logo em seguida do nó cabeça,
de forma que o nó cabeça sempre aponte para o novo elemento.
*/
cabeca->proximo = novo;
// Por praticidade, vamos retornar um ponteiro para o novo elemento inserido dentro da lista
return novo;
}
- Função de remoção (Remover o primeiro elemento encontrado)
// Remove o primeiro elemento que contém um determinado valor
int remover(Noh *cabeca, int valor) {
// Só pode tentar remover da lista caso ela não seja vazia.
// Retorna '\0' indicando que o nó de conteúdo "valor" não foi encontrado.
if (cabeca->proximo == NULL) {
return '\0';
}
Noh *atual;
atual = cabeca->proximo;
/*
Considerando que temos a seguinte lista: [Nó cabeça]->[8]->[15]->[46]->[7]->NULL
e que queremos remover o número 15.
Para isso acontecer, o elemento de conteúdo [8] deverá apontar para
o elemento de número [46], removendo o elemento [15] da lista e
ficando assim: [Nó cabeça]->[8]->[46]->[7]->NULL
*/
// Se o primeiro elemento tiver conteúdo igual ao valor, vamos
// fazer o nó cabeça apontar para o nó correto.
if (atual->conteudo == valor) {
//Antes da remoção: [Nó cabeça]->[Atual]->[Outro]->NULL
//Depois da remoção: [Nó cabeça]->[Outro]->NULL
cabeca->proximo = atual->proximo;
int conteudo = atual->conteudo;
// Não basta apenas remover o nó da lista, temos que desocupar o espaço que esse nó
// estava ocupando na memória principal (Heap), para não termos vazamento de memória.
free(atual);
return conteudo;
}
/*
Caso o elemento esteja no meio da lista, precisa percorrer a lista
até encontrar o elemento a ser removido.
Um cuidado é:
Se temos a lista: [Nó cabeça]->[8]->[15]->[46]->[7]->NULL
e o elemento a ser removido é o [46], não podemos percorrer a lista
até chegar no [46], pois dessa forma não conseguiremos fazer
o elemento [15] apontar para o "próximo nó" do nó [46], já que não
temos um ponteiro apontando para o [15].
Para realizar essa função corretamente, temos que percorrer a lista
até chegar no nó anterior ao elemento que queremos remover.
Assim, iremos conseguir manter a estrura correta da lista.
Ex:
Nó anterior ao [46] que vamos remover
|
Antes de remover: [Nó cabeça]->[8]->[15]->[46]->[7]->NULL
Depois de remover: [Nó cabeça]->[8]->[15]->[7]->NULL
*/
while (atual != NULL && atual->proximo != NULL) {
// Se encontrou o nó a ser removido no meio da lista
if (atual->proximo->conteudo == valor) {
Noh *paraRemover = atual->proximo;
int conteudo = paraRemover->conteudo;
// No exemplo anterior, faz o [15] apontar para o próximo do [46]
atual->proximo = paraRemover->proximo;
// Libera memória utilizada pelo elemento removido da lista
free(paraRemover);
return conteudo;
}
// Enquanto não encontrou o nó para remover e não chegou no fim da lista, passa
// para o próximo nó e repete o processo
atual = atual->proximo;
}
// Se não tiver elemento na lista com o conteúdo sendo o valor.
return '\0';
}
- Função para imprimir
A função para imprimir os elemento é muito simples, basta percorrer
cada nó imprimindo o seu conteúdo.
(Avança para o próximo nó até encontrar NULL)
void imprimir(Noh *cabeca) {
// Começando do primeiro nó
Noh *atual = cabeca->proximo;
// Percorre todos os nós da lista, imprimindo o conteúdo de cada um.
while(atual != NULL) {
printf("%d ", atual->conteudo);
atual = atual->proximo;
}
}
4 - Arquivo main.c
Agora, para testar a lista criada, segue o arquivo main.c
#include <stdio.h>
#include <stdlib.h>
#include "TadLista.h"
int main() {
Noh * cabeca;
cabeca = criar();
inserir(cabeca, 7);
inserir(cabeca, 46);
inserir(cabeca, 15);
inserir(cabeca, 8);
imprimir(cabeca); //Resultado: 8 15 46 7
remover(cabeca, 46);
printf("\nAo remover [46]: ");
imprimir(cabeca); //Resultado: 8 15 7
}
5 - Rodando a lista implementada!
- Dentro do terminal na pasta onde os arquivos TadLista.h, TadLista.c e main.c estão, digite:
gcc -c main.c TadLista.cpara compilar esses arquivos e criar os arquivos "objetos"/".o". - Em seguida, digite:
gcc -o programa main.o TadLista.opara criar o arquivo executável - Por fim, basta digitar
./programapara ver o resultado no terminal!
Final
Se você chegou até aqui com sua lista completa, parabéns pela determinação! 🎉
Caso tenha gostado do tópico de estruturas de dados e deseja mais conteúdo como esse (ou qualquer outro tema), deixe seu comentário 🗨 aqui em baixo com sugestões para mais publicações.