Estrutura de dados 2 – Lista

Quem nunca teve o problema clássico de ter que armazenar uma quantidade X de valores, sem limite máximo e com buscas, remoção e adição em qualquer lugar de forma rápida? Pois bem as listas estão ai exatamente para isso. Claro, poderíamos criar um vetor com um número X, e caso precisa-se, utilizaríamos realloc() para aumentar o vetor. Porém, qualquer coisa que fizéssemos com um vetor (ordernar, busca, remoção, adição) é muito custosa, uma lista ligada nos permite fazer isso de forma rápida, customizáda, e econômica. Vamos explicar aqui a lista duplamente ligada, uma das mais completas, porém vamos mostrar também a teoria de suas variações (lista ligada e lista circular).

Uma lista duplamente ligada nada mais é do que uma estrutura de dados que contém um ponteiro para um próximo nó e um nó anterior, dessa forma:

typedef struct node{
int val;
struct node *next;
struct node *prev;
}node;

Isso nos mostra que cada nó de nossa lista possuirá um ponteiro para nós adiante e anteriores, nos dando um desenho de uma lista dessa forma:
               ________        ________
               |___A___|       |___B___|
               |__next__|—->|__next__|—>NULL
NULL<–|__prev__|<—-|__prev__|
Pode parecer um pouco complexo no início, e realmente é, porém com um pouco de prática e escovação de bits, a idéia fica simples. O grande problema é entender ponteiros, e conseguir entender como isso é melhor de que um vetor de duas posições. Vamos por partes.
Ponteiros.
Ponteiros são uma ferramenta maravilhosa de programação, a prática nua e crua diz que ponteiros são exatamente isso, ponteiros para uma posição de memória. Tudo que fazemos, tem que estar na memória do computador, se por exemplo temos o código:
int x;
x estará em algum lugar da memória do computador, para sabermos isso podemos utilizar o operador de endereço (&), ou criar um ponteiro “literal” dessa forma:
int x;
int *px = x;
Dessa forma, se x está na posição 0x0840abff, então px conterá o endereço 0x0840abff, assim como &x irá apontar para o mesmo endereço. Agora você deve estar se perguntando: “uau, que legal….o que eu faço com isso?”, pois bem, no nosso caso, é necessário pois como não sabemos o tamanho inicial de nossa lista, e a memória do computador é um lugar bem caótico, um ponteiro para next como é no nosso caso aponta para o próximo valor armazenado na lista, dessa forma, não perdemos absolutamente nada. O ponteiro prev, aponta para o nó imediatamente anterior, acho que ficou bem claro que podemos “caminhar” tanto para a direita (next) quanto para a esquerda (prev) com uma lista duplamente ligada não?
A mágica das listas está justamente nessa “caminhada” que fazemos indo para o próximo nó (next), ou o nó anterior, e podemos fazer isso com uma atribuição de ponteiros:
node *n = cria_no();
node *next = NULL;
adiciona(n,’a’);
adiciona(n,’b’);
next=n->next;
Nesse código, primeiramente iniciamos a lista criando um nó vazio com a função cria_no(), que normalmente é criada utilizando-se malloc(), logo em seguida criamos um ponteiro do tipo node chamado next, adicionamos na nossa lista dois valores (a e b), e falamos que next é o segundo valor da lista, sabemos que ele é o segundo valor da lista pois a nossa função de adição adiciona sempre no final da lista. Não sei se consegui demonstrar a praticidade e facilidade que é termos uma lista duplamente ligada, mas acredito que o código que se encontra aqui possa explicar melhor, assim como as funções de contagem de tamanho (size()), adição (add_node()), remoção (rem_node()), busca (search()) e deleção completa da lista (delete_list()).
As diferenças para as listas simples e listas circulares são os ponteiros, uma lista simples não possui o ponteiro prev, economizando a memória em grandes sistemas, e facilitando a busca em sistemas onde não nos importamos muito com o que já passou, pois sempre veremos a lista desde o começo. Listas circulares são um pouco mais complicadas, elas possuem um terceiro ponteiro no último nó, que aponta para o primeiro nó. A atualização e manutenção desse tipo de lista é cara e um pouco mais complexa, porém são muito úteis em sistemas de buscas, como por exemplo busca em um histórico, onde o usuário pode sempre ir pra frente e ficar, litealmente, “dando voltas” na lista até escolher alguma coisa ou ficar satisfeito com o que vê.
Enfim, listas são importantíssimas, pois com a magia dos ponteiros podemos ter praticamente qualquer dado representado inúmeras vezes, e nos preocuparmos apenas com as coisas básicas do mesmo, em nosso programa.

About Zarnick

Programer, sysadmin, guitarrist, and Italian. That's what I am. Plain simple.
ANSI C, C/C++, Tutorials , , , , , , , ,