Anteriormente, falei um pouco sobre vetores, que nada mais é que um espaço contiguo reservado na memória para armazenar elementos de um tipo especifico de variável. Entretanto, o vetor não é muito flexível, porque o desenvolvedor tem que dimensiona-lo com o número máximo de elemento que pode ser usado. Isso pode fazer com que o espaço reservado seja subutilizado ou até mesmo não ser suficiente para armazenar todos os elementos necessários. 

Numa lista encadeada, para cada novo elemento inserido, alocamos um espaço de memória para armazená-lo. Entretanto, não podemos garantir que a lista encadeada será armazenada de forma contigua.

Para podermos percorrer todos os elementos de uma lista, é necessário armazenar em cada elemento, o próximo elemento da lista. A estrutura consiste numa sequência encadeada de elementos, chamada de nó da lista. O último elemento da lista aponta para NULL, sinalizando que não a mais elementos.

Para podermos exemplificar a lista em C, vamos considerar um exemplo simples, em que queremos apenas armazenar valores inteiros numa lista encadeada.

struct lista {

                int info;

                struct lista *prox;

};

typedef struct lista Lista;

Devemos notar que trata-se de uma estrutura auto-referenciada, pois além de armazenar o valor inteiro, ele também tem um ponteiro que apontar para a próxima estrutura do mesmo tipo e typedef struct lista Lista cria o tipo Lista que representa um nó da lista encadeada. 

Nas próximas postagens eu vou explicar como usar a lista encadeada.