Listas Encadeadas

Aprenda a implementar uma lista encadeada completa, incluindo operações de adição, remoção e busca de elementos, seja no início, meio ou fim.
Primeiramente, veja como funciona uma lista encadeada através da imagem abaixo:

Os retângulos acima são chamados de nós(ou nodes, em inglês) da lista, os quais são compostos de um valor e um ponteiro para o próximo nó. Perceba que, é necessário um ponteiro para guardar o primeiro nó da lista(conhecido como a cabeça da lista), na representação acima o mesmo foi chamado de head. Já o ultimo nó da lista aponta para nada(NULL).

Agora vamos iniciar a implementação da lista em C, irei mostrar a implementação para uma lista de números inteiros, mas fica seu critério escolher o tipo de dado.

Para representar um nó, podemos criar uma struct, da seguinte maneira:

	typedef struct node{
	int value;//valor armazenado no nó
	struct node* prox;//ponteiro para o próximo nó da lista
	}node;

view raw node.c hosted with ❤ by GitHub

Como exposto acima, é necessário armazenar o primeiro nó da lista. É possível fazer isto de duas maneiras: fazendo um simples ponteiro ou armazenando um ponteiro em uma struct, que pode guardar mais algumas informações, como o tamanho da lista, por exemplo. Veja abaixo a implementação com struct:

	typedef struct{
	node* head;//ponteiro para o primeiro nó da lista
	int tamanho;//número inteiro que armazena a quantidade de elementos adicionados à lista
	}list;

view raw list.c hosted with ❤ by GitHub

Inicialização

É necessário inicializar os valores da lista antes de utilizá-la, já que, as variáveis estarão armazenando algum lixo de memória, o que traria problemas para a variável tamanho que deve ser iniciada com o valor 0 e é importante iniciar a cabeça com NULL, para "sabermos" se a lista está vazia(head = NULL). Para isso, vamos criar a função init:

	void init(list* l){
	l->tamanho = 0;//o tamanho inicia como 0
	l->head = NULL;//a cabeça da lista inicia como NULL
	}

view raw init.c hosted with ❤ by GitHub

Inserção

Há três tipos de inserção em uma lista encadeada, inserção no inicio, no fim e definida por número, veja a descrição e o algoritmo de cada uma destas a seguir:

• No inicio

Esta é a mais simples das três, basta definir o nó inserido como a cabeça da lista e definir como seu próximo a atual cabeça da lista:

	void insere_inicio(list* l, int value){
	node* no = malloc(sizeof(node));//aloca memória para o nó a ser inserido
	no->prox = l->head;//define como o proximo a atual cabeça da lista
	no->value = value;//insere o valor dado no nó
	l->head = no;//define a cabeça da lista como o nó(insere-o no inicio)
	}

view raw insere_inicio.c hosted with ❤ by GitHub

• No fim

Para fazer esta inserção, é preciso lembrar que o ultimo nó da lista é aquele que aponta para NULL, veja novamente a imagem no inicio da postagem. Assim, basta ir percorrendo a lista até encontrar um nó que aponta para NULL e redefinir o prox para o no que será inserido, e já que estamos inserido no final, o nó a ser inserido deve apontar para NULL.

	void insere_fim(list *l,int value){
	node* no = malloc(sizeof(node)),*aux=l->head;//alocando memória para o nó a ser inserido e criação de um nó auxiliar/
	no->prox=NULL;//como o nó será inserido no final, o mesmo terá como próximo "Nada"
	no->value=value;//inserindo o valor dado no no
	while(aux->prox != NULL)//percorrendo a lista até encontar o ultimo nó
	aux = aux->prox;
	aux->prox = no;//definindo como o próximo do ultimo nó o nó que está sendo inserido
	}

view raw insere_fim.c hosted with ❤ by GitHub

• No meio

Nesse caso, é preciso que seja dado um índice n para inserir o novo nó na enésima posição da lista.Aqui irei considerar o índice 0 como a primeira posição da lista, assim como acontece em um vetor.

	void insere_meio(list *l,int value,int index){
	if(index == 0)insere_inicio(l,value);
	else{
	int i;
	node *no = malloc(sizeof(node)),*aux = l->head;
	for(i=0;i<index-1;i++){
	aux = aux->prox;
	}
	no->value = value;
	no->prox = aux->prox;
	aux->prox = no;
	}
	}

view raw insere_meio.c hosted with ❤ by GitHub

Remoção

Existem vários tipos de remoção, alem dos tipos de inserção(inicio, por índice e fim), há tambem a remoção dado um valor, na qual o primeiro nó com este valor será removido da lista;

• No inicio

Para remover do inicio, siplesmente mudamos a cabeça da lista para o proximo nó após a cabeça e,claro, desalocar o nó removido. Veja o código:

	void remove_inicio(list* l){
	node* no = l->head;//criando um ponteiro de nó auxiliar que aponta para a cabeça da lista
	l->head = no->prox;//modificando a cabeça da lista para o segundo elemento da mesma
	free(no);//desalocando a memória do nó removido
	}

view raw remove_inicio.c hosted with ❤ by GitHub

• No fim

Só é preciso percorrer a lista até chegar ao penultimo elemento, mudar seu proximo para NULL e desalocar o último nó.

	void remove_fim(list* l){
	node* no = l->head,*aux;
	//Observe que no ultimo no, seu proximo é NULL, como queremos o nó anterior ao ultimo, utilizamos no->prox->prox.
	while((no->prox)->prox != NULL){//percorrendo a lista até chegar ao penultimo nó
	no = no->prox;
	}
	aux = no->prox;//aux será utilizado para desalocar o nó retirado
	no->prox = NULL;//definindo que o proximo elemento do penultimo nó(agora ultimo) é NULL
	free(aux);//desalocando o nó removido
	}

view raw remove_fim.c hosted with ❤ by GitHub

• Dado um valor


Nesse caso, é necessário percorrer a lista até encontrar um nó cujo seu próximo tenha o valor dado e redefinir seu próximo para o próximo do que está sendo removido.Veja a imagem acima e o código abaixo:

	void remove_m(list *l, int valor){
	node* no = l->head,*aux;
	if(no->value == valor){remove_inicio(l);return;}//se o no com o valor dado for a cabeça, remove do inicio
	//buscando o no anterior ao que será removido
	while(no->prox->value != valor && no->prox!=NULL){
	no = no->prox;
	}
	//verificando se foi encontrado algum nó com o valor dado, se sim imprime um aviso e acaba a função com o return.
	if(no->prox == NULL){printf("Não foi encontrado este valor na lista!\n");return;}
	aux = no->prox;//iniciando o nó auxiliar, que será utilizado para desalocar o nó removido
	no->prox = aux->prox;//retirando o elemento da lista, fazendo com que o seu antigo antecessor tenha como próximo seu sucessor
	free(aux);//desalocando o nó retirado
	}

view raw remove.c hosted with ❤ by GitHub

Busca

A busca consiste em, dado um valor a função retorna o primeiro nó que o contem, o código é bem simples, basta percorrer a lista até encontrar um nó que tem aquele valor e retorná-lo, caso não exista um nó com o valor dado, a função retorna NULL, veja:

	node* search(list *l,int value){
	node *no=l->head;//no utilizado para percorrer a lista
	while(no != NULL && no->value != value){//percorre a lista até encontrar um nó com o valor dado ou chegar ao fim da mesma
	no = no->prox;
	}
	if(no->value = value)return no;//retorna o no, se encontrado
	else return NULL;//retorna NULL, caso nao exista um no com tal valor na lista
	}

view raw search.c hosted with ❤ by GitHub

Impressão

Função simples que percorre a lista, imprimindo os valores de seus elementos:

	//Essa função imprimirá a lista dessa forma: {no1,no2,no3,no4...}
	void print(list* l){
	node* no = l->head;
	printf("{");
	printf("%d",no->value);no=no->prox;//imprimindo o primeiro no antes pra nao sobrar uma virgula no inicio ou final.
	while(no!=NULL){//percorrendo a lista e imprimindo os nós
	printf(",%d",no->value);
	no=no->prox;
	}
	printf("}\n");
	}

view raw print.c hosted with ❤ by GitHub

Se encontrar algum erro ou tiver alguma dúvida, faça um comentário!