Listas Duplamente Encadeadas

A lista duplamente encadeada possui maior facilidade de acesso aos nós da lista possibilitando uma maior manipulação das informações e da própria lista. Esse conceito utiliza os mesmos conceitos de listas vistos, porém a lista possui outro ponteiro que auxilia na busca das informações na lista.
struct no
{
struct no * esq;
int info;
struct no *dir;
}; typedef struct no lista

É necessário redefinir a estrutura do nó da lista com um novo ponteiro que irá apontar para o nó anterior e com isso interligará a lista em que pode obter uma busca tanto para direita da lista como para a esquerda da lista.

O nó duplamente encadeado possui a vantagem de auxiliar o programador nas implementações da lista em que agora tem uma maior facilidade de encontrar informações dentro da lista.

void cria_listadupla (Lista * * inicio, Lista * * fim)
{
*inicio = NULL;
*fim = NULL;
}



Na criação da lista continua com o conceito de lista encadeada em que os ponteiros “inicio” e “fim” permanecem com valores nulos para a que a lista possa ser iniciada.

Para inserir novos valores na lista duplamente encadeada é necessário que os ponteiros que apontam para o próximo nó e para o anterior estejam devidamente programados para que a lista não possua ponteiros inutilizados com a inserção de novos nós.

void ins_inicio (Lista * * inicio, Lista * * fim, int v)
{
Lista * p;
p = (Lista * ) calloc (1, sizeof (Lista));
p-> info = v;
p-> esq = NULL;
p-> dir = *inicio;
if (*inicio = = NULL)
*fim = p;
else
(*inicio)-> esq = p;
*Inicio =p;
}

Esse método de inserção de valores insere novos valores no inicio da lista em que agora é preciso que o novo ponteiro que aponta para o nó anterior precisa ser definido. O ponteiro “p” que aponta “esq” recebe um valor nulo, pois caracteriza como o inicio da lista e não possui outros valores anteriores ao primeiro nó.

No caso de inserir novos valores o método verifica se a lista já possui algum nó na lista, caso não exista o nó a ser inserido é o primeiro e os ponteiros “inicio” e “fim” estarão no primeiro nó, porém caso já exista algum nó na lista o ponteiro “esq” irá apontar para o nó anterior que está sendo inserido na lista o ponteiro “inicio” auxilia a definir o nó como primeiro e novo nó pode ser acoplado à lista.

void ins_fim (Lista * *inicio, Lista * *fim, int v)
{
Lista *p;
p = (Lista *) calloc (1,sizeof(Lista));
p-> info = v;
p-> dir = NULL;
p-> esq = *fim;
if (*inicio == NULL)
*inicio = p;
Else
(*fim)-> dir = p;
*fim = p;
}

O método de implementação descrito insere novos valores no final da lista em que o ponteiro “dir” nesse caso será atribuído o valor nulo para identificar o nó como o último nó da lista.

É também verificado se a lista já possui algum nó com isso é analisado se o ponteiro “inicio” está apontando para algum nó, se não estiver apontando, ou seja, o ponteiro “inicio” é nulo, então significa que a lista não contem nó e então o ponteiro “inicio” e “fim” estarão no primeiro nó da lista, no entanto se o ponteiro “inicio” não é “nulo” então o ponteiro “dir” apontará para o próximo nó da lista com o auxílio do ponteiro “fim” e por fim o novo nó inserido será o último nó da lista.

A lista duplamente encadeada é o melhor método de listas visto que facilita o programador na implementação de métodos que aumentam a capacidade de armazenar mais informações da lista de forma que essas informações possam ser encontradas com uma maior praticidade e também na organização dessas informações.