Uma das coisas mais básicas em programação, é a utilização de uma lista ligada para armazenar dados. O único grande problema da lista ligada, são os famigerados ponteiros.

 Ponteiros

Por incrível que pareça, ponteiros são extremamente simples, sua teoria pelo menos.
Ponteiros nada mais são do que apontadores para endereços de memória. Por exemplo, digamos que queremos uma função que receba um vetor de inteiros, altere de alguma forma, e retorne o mesmo vetor, como fazer?
Essa é uma situação bem típica, onde a utilização de ponteiros vem a calhar, vamos mostrar um código, e depois explicar aos poucos.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#define MAX 10
int *modifica(int *v, int n){
  unsigned int i = 0;
  for(i=0;i<n;i++){
    v[i]=10;
  }
  return v;
}
int main(void){
  int *vetor = NULL;
  if((vetor=malloc(sizeof(int)*MAX))==NULL){
    perror("malloc");
    return errno;
  }
  memset(vetor,'\0',sizeof(int)*MAX);
  vetor=modifica(vetor,MAX);
  free(vetor);
  vetor=NULL;
  return 0;
}


Vamos explicar o código aos poucos.
Primeiramente, quando declaramos um vetor, como por exemplo:

int vetor[10];

Estamos na realidade reservando um endereço de memória com uma capacidade de armazenar 10 valores inteiros. Porém não estamos fazendo isso, ao invés, estamos declarando um ponteiro para uma variável do tipo int, e logo em seguida alocando dinâmicamente a memória. Alocação dinâmica é um assunto para um post futuro, inicialmente, vamos apenas mostrar qual é a função, e o quotar o manual da função:

void *malloc(size_t size);

malloc() allocates size bytes and returns a pointer to the allocated memory. The memory is not cleared.

Ok, primeiramente, se essa função é do tipo void, como ela pode retornar algo?
Void não quer dizer que não retorna, apenas que não sabemos o que retorna, essa função alloca um espaço de memória, e retorna um ponteiro para o início da posição de memória alocada, como já falamos anteriormente, mas então, como é a cara de um ponteiro?

Look up, up to the stars.

Exatamente, podemos declarar um ponteiro apenas adicionando * na declaração, ou seja, quando temos no nosso código:

int *vetor = NULL;

Na realidade estamos declarando um ponteiro, do tipo int para um endereço de memória que inicia em NULL(0×0). Ao chamarmos malloc e retornarmos um ponteiro do tipo void, para a memória alocada, fazemo um typecast para um int, e temos nosso vetor, exatamente da mesma forma que teríamos se fosse declarado dessa forma:

int vetor[10];

Após termos isso, limpamos a memória com a função memset(), e agora podemos utilizar nosso vetor, e no final, precisamos limpar a memória utilizando free().
Na realidade não precisávamos ter feito tudo isso, porém, dessa forma, temos um ponteiro, demonstramos alocação dinâmica, e ganhamos alguns pontos de 313373.
Obviamente, vocês já devem ter percebido que a nossa função para modificar um vetor, também possui um ponteiro, ou seja:

int *modifica(int *v, int n);

Podemos ver que ela recebe um ponteiro para um inteiro, e retorna um ponteiro para um inteiro, logo, se passarmos o nosso ponteiro previamente alocado, a variável v na função modifica recebera um endereço de memória, o mesmo que a nossa variável vetor aponta, logo podemos utilizar o mesmo, modificando o valor dessa variável, e no final, retornamos o mesmo ponteiro, que pode ser pego pela variável vetor, ou outra variável, não precisaríamos ter feito esse retorno, porém dessa forma nosso código fica mais portável para ser utilizado em qualquer situação.
Existe muito mais para falar sobre ponteiros, porém por hora, isso é o suficiente para entendermos a idéia básica da lista ligada.

A lista

Uma lista ligada, nada mais é do que uma estrutura para armazenar uma quantidade n de dados, de preferência de forma dinâmica, e de rápido acesso.
Ou seja, precisaremos de uma struct com algumas coisas dentro dela:


typedef struct Node{
  int num;
  struct Node *next;
}Node;


Iremos chamar cada ítem da nossa lista de Node(nó), dentro dessa estrutura podemos ter qualquer coisa, porém precisamos ter um ponteiro para uma nova estrutura do tipo Node, ou seja, nosso próximo ítem. Dessa forma, uma lista já previamente inicializada seria por exemplo:

[1]->[2]->[3]->[4]->…[n]->NULL

Onde -> é o ponteiro *next, e [n] é o nosso num. Repare que o último ponteiro aponta na realidade para NULL(0×0), finalizando nossa lista.
Agora tudo que precisamos é de duas funções, uma para criar a lista, e outra para adicionar um nó.


struct Node *create(struct Node *list, int number); //Cria a lista
struct Node *addNode(struct Node *list, int number); //Adiciona um nó na lista


Internamente, as funções são:


struct Node *create(struct Node *list, int number){
  //Se a lista não for null, devemos retornar NULL
  if(list!=NULL)
    return NULL;
  if((list=(struct Node*)malloc(sizeof(struct Node)*1))==NULL){
    perror("malloc");
    return NULL;
  }
  memset(list,'\0',sizeof(struct Node)*1); //Devemos limpar a lista antes de enviar de volta
  list->num=number;
  list->next=NULL;
  return list;
}


e


struct Node *addNode(struct Node *list, int number){
  struct Node *tmp = NULL;
  struct Node *start = NULL;
  if(list==NULL){ //Se a lista for NULL, vamos iniciar a mesma
    if((list=create(list,number))==NULL){
      return NULL;
    }
  return list;
  }
  //Armazenando o inicio
  start=list;
  //Caminhando até o nó final
  while(list->next!=NULL){
    list=list->next;
  }
  //Alocando memória para o novo nó
  if((tmp=(struct Node *)malloc(sizeof(struct Node)*1))==NULL){
    perror("malloc");
    return NULL;
  }
  memset(tmp,'\0',sizeof(struct Node)*1);
  tmp->num=number;
  tmp->next=NULL;
  //Adicionando o nó à lista
  list->next=tmp;
  return start;
}