Lista simplesmente ligada

Listas ligadas são um outro tipo de estrutura de dados, e em conjunto com as estruturas nativas da linguagem de programação, vetores e matrizes, visam manejar e organizar os dados de um determinado modo. As listas ligadas foram criadas para contornar o problema de estruturar os dados em vetores e matrizes, que dispondo os dados de modo sequencial, com acesso indexado, apresentam a desvantagem de lenta velocidade de inserção e remoção de elementos, visto que é preciso alterar todo o conjunto em caso de uma remoção no inicio de um vetor, reposicionando todos os demais, o que consome muito tempo de computação.




Já as listas ligadas, por serem criadas dinamicamente, por alocação de memoria em tempo de execução, tem a vantagem de alocar um novo elemento no inicio, final ou meio da lista sem ter que alterar todo o conjunto de elementos, somente localizando a posição correta de inserção e definindo os novos ponteiros que manterão a lista coesa.

As listas são representadas por nodos ou nós, que são em geral structs com dados que serão armazenados na lista, por exemplo, uma lista onde cada nó possua o cadastro de um cliente, e os ponteiros que ligam estes nós uns aos outros, veja o exemplo:

struct cliente{
int id; // identificação do cliente
char nome[30];
float totalCompra;
struct cliente *prox, *ant;
};

O nó representado por cliente, possui dois ponteiros, denominados *prox e *ant, que visam guardar o endereço de memoria do nó anterior e do nó posterior ao nó considerado atual, assim, possuindo as referencias, é possivel caminhar na lista, de modo que um ponteiro tendo o endereço do seguinte, aponta para o proximo, e dessa forma sucessivamente, até alcançar o final da lista, sinalizado por um ponteiro que guarda NULL.

Nos proximos posts sobre listas ligadas apresento os codigos de inserção, remoção e busca. Antes de implementá-los, vale ressaltar que há dois modos de criar listas ligadas, usando C, totalmente estruturado, e C++, orientado a objeto, com a possibilidade de definir templates, e utilizar-se do recurso de tipos genericos ( gabaritos ) para criar listas para diversos tipos, int, float, double, char, sem a necessidade de codificar uma lista para cada um.