Dando continuidade em nossa seção sobre estrutura dinâmica de dados e ao tutorial passado sobre Listas simplesmente encadeadas, onde criamos e ensinamos a colocar nós ao fim e no início da lista, e depois como retirar nós do início e do fim de uma lista, vamos agora mostrar como colocar elementos em qualquer ponto da lista, bem como tirar nós do início, do fim e de qualquer lugar da lista.

[Image] Listas em C
Leia este tutorial no seu computador ou celular: Apostila C Progressivo Como criar uma lista completa em C Agora que você já deve ter se familiarizado com os conceitos e lógicas de tirar e inserir elementos em uma lista, vamos fazer algumas mudanças, deixar o programa mais robusto e flexível.

Já no tutorial passado, na parte de inserir elementos, criamosa a função aloca(), que como o próprio nome diz, ela vai alocar espaço para uma estrutura, um nó em nossa lista.
Ela pede para inserir o número, colocar na variável 'num' da struct e retorna o endereço alocado dinamicamente.

Agora, criamos também a variável global tam, que irá armazenar o tamanho de nossa lista.
Ou seja, quantos nós tem nossa lista. E para contabilizar isso, toda vez que criamos um nó, incrementamos essa variável.
Analogamente, sempre que tiramos uma struct da lista, decrementamos a variável.

Alteramos também a função exibe, que agora exibe a ordem dos elementos na lista.
Conforme podemos ver na imagem no início deste tutorial.



Como inserir nós em qualquer posição da lista Vamos agora mostrar como criar a função insere() que recebe a LISTA e pergunta ao usuário em que posição o usuário quer inserir o elemento na lista. Ou seja, se queremos inserir na posição 'n', o elemento vai ficar nessa posição 'n' e o que estava lá antigamente vai para frente, para posição 'n+1'.
O usuário vai dizer a posição e está sera armazenada na variável pos.

Podemos inserir desde a posição 1 até a 'tam'.
Obviamente, fora desse intervalo devemos mostrar uma mensagem de erro.
Feita essa verificação da posição, vamos adicionar o elemento na dita posição.

Caso seja posição 1, não devemos nos estressar.
Afinal, inserir um elemento na posição 1 é inserir uma estrutura no início da lista, e já criamos uma função para isto, a insereInicio(), bastando chamar ela: insereInicio(LISTA);

Caso seja em qualquer outra posição, a coisa fica mais trabalhosa.
O segredo para isto é identificar dois elementos.o anterior e o elemento que está naquela posição.

Por exemplo, se queremos colocar um nó na terceira posição, devemos guardar essa posição e a anterior, pois iremos fazer o segundo elemento apontar para o novo nó, e fazer esse novo nó apontar para aquele que estava na terceira posição.

Para isso vamos usar dois ponteiros do tipo node, o tipo de nossa estrutura: o 'atual' e o 'anterior'.
O atual começa no primeiro nó da LISTA, e o anterior não está em uma posição anterior (um aponta para LISTA->prox e o outro para LISTA).

Agora temos que fazer estes dois pontos 'correrem' pela lista até chegar onde queremos.
Vamos usar um laço for para isso, e em cada iteração fazemos o seguinte:
Fazemos o ponteiro 'anterior' receber o ponteiro 'atual', e depois fazemos o 'atual' receber o próximo elemento da lista, que é o 'atual->prox'.

Se queremos chegar na posição 4, por exemplo, devemos fazer esse procedimento 3 vezes, pois partimos da primeira posição da lista. Ou seja, fazemos isso (pos - 1) vezes, e ao final deste procedimento, o ponteiro 'atual' estará no elemento que mudará de posição (para frente), e o ponteiro 'anterior' apontará para a posição anterior:
for(count=1 ; count < pos ; count++){ anterior=atual; atual=atual->prox; }
E agora vamos inserir nosso nó, que criamos ao declarar o ponteiro 'novo' e fazer ele receber um bloco alocado pela função aloca().
Vamos lá, devagar pois não é tão simples.

Temos dois nós: o 'atual' e o 'anterior'. Queremos colocar um novo nó, o 'novo', no lugar do nó 'atual' e empurrar o 'atual' pra frente.
Para isso, devemos pegar o 'anterior' e fazer apontar para o 'novo': anterior->prox = novo;
E o novo nó deve apontar para o que estava nesse posição: novo->prox = atual;
E claro, incrementar o tamanho da lista: tam++;

Pronto. Já podemos colocar um nó no início, no fim ou em qualquer lugar de nossa lista :)
Vamos para o próximo passo: retirar elementos de nossa lista.

Como retirar estruturas de uma lista Se já leu todos nossos tutoriais sobre listas em C, certamente já deve ter em mente como implementar um algoritmo que retire um elemento.

Vamos usar exatamente a mesma ideia que usamos na parte passada do tutorial, para achar os elementos 'atual' (que vamos excluir) e o anterior a ele.
Ou seja, aquele mesmo laço while será usado, da mesma maneira.

Porém, não vamos precisar de um novo nó, afinal não vamos adicionar nada, e sim retirar a struct apontada pelo ponteiro 'atual'.
E como vimos diversas, o ato de 'retirar' um nó de uma lista é simplesmente deixar de apontar algum elemento da lista para ele.

Quem aponta para o elemento que queremos retirar é: anterior->prox
Qual elemento que vem após o elemento que vamos retirar: atual->prox
Elemento retirado, que devemos retornar da função: atual

Ou seja, para excluir, basta apontarmos o elemento anterior ao que queremos retirar, para aquele elemento que vem DEPOIS do que queremos retirar.
Isso é feito da seguinte maneira: anterior->prox = atual->prox

E pronto. A lista continua ligada, mas sem o elemento 'atual', na qual retornamos, sem antes decrementar a variável tam, já que retiramos uma estrutura da lista.

Código completo de uma Lista em C E finalmente, após muito estudo e trabalho, nosso código completo, de uma lista em C que nos permite inserir e retirar um nó (struct) de toda e qualquer posição.

É uma lista flexível, onde há diversas maneiras de trabalhar com ela, além de exibir seus elementos de uma maneira esteticamente agradável e faz uso de pouca memória (além de liberar ela, ao final da aplicação), sendo robusta e muito e eficiente:

#include <stdio.h> #include <stdlib.h> struct Node{ int num; struct Node *prox; }; typedef struct Node node; int tam; 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); void insere (node *LISTA); node *retiraInicio(node *LISTA); node *retiraFim(node *LISTA); node *retira(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; tam=0; } 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. Escolher onde inserir\n"); printf("6. Retirar do inicio\n"); printf("7. Retirar do fim\n"); printf("8. Escolher de onde tirar\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: insere(LISTA); break; case 6: tmp= retiraInicio(LISTA); printf("Retirado: %3d\n\n", tmp->num); break; case 7: tmp= retiraFim(LISTA); printf("Retirado: %3d\n\n", tmp->num); break; case 8: tmp= retira(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; } tam++; } void insereInicio(node *LISTA) { node *novo=aloca(); node *oldHead = LISTA->prox; LISTA->prox = novo; novo->prox = oldHead; tam++; } void exibe(node *LISTA) { system("clear"); if(vazia(LISTA)){ printf("Lista vazia!\n\n"); return ; } node *tmp; tmp = LISTA->prox; printf("Lista:"); while( tmp != NULL){ printf("%5d", tmp->num); tmp = tmp->prox; } printf("\n "); int count; for(count=0 ; count < tam ; count++) printf(" ^ "); printf("\nOrdem:"); for(count=0 ; count < tam ; count++) printf("%5d", count+1); 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; } } } void insere(node *LISTA) { int pos, count; printf("Em que posicao, [de 1 ate %d] voce deseja inserir: ", tam); scanf("%d", &pos); if(pos>0 && pos <= tam){ if(pos==1) insereInicio(LISTA); else{ node *atual = LISTA->prox, *anterior=LISTA; node *novo=aloca(); for(count=1 ; count < pos ; count++){ anterior=atual; atual=atual->prox; } anterior->prox=novo; novo->prox = atual; tam++; } }else printf("Elemento invalido\n\n"); } 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; tam--; 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; tam--; return ultimo; } } node *retira(node *LISTA) { int opt, count; printf("Que posicao, [de 1 ate %d] voce deseja retirar: ", tam); scanf("%d", &opt); if(opt>0 && opt <= tam){ if(opt==1) return retiraInicio(LISTA); else{ node *atual = LISTA->prox, *anterior=LISTA; for(count=1 ; count < opt ; count++){ anterior=atual; atual=atual->prox; } anterior->prox=atual->prox; tam--; return atual; } }else{ printf("Elemento invalido\n\n"); return NULL; } }