Listas Ligadas - Parte 6

Listas Duplamente Ligadas

Uma desvantagem da lista ligada simples é que podemos seguir os links apenas em uma direção. Por exemplo, nas rotinas de inserção tivemos que usar duas variáveis, uma para guardar o endereço do nó atual e outra para guardar o endereço do nó anterior.

Na lista duplamente ligada armazenamos em cada nó dois ponteiros, um para o próximo nó e outro para o anterior. Ficamos com algo assim:

// estrutura de um elemento (nó) da lista
typedef struct no_lista
{
 int      valor; // dado do elemento
 no_lista *prox; // ponteiro para o elemento seguinte
 no_lista *ant;        // ponteiro para o elemento anterior
} NO;

// variavel que aponta para o início da lista
NO inicio; // inicio.prox aponta para o primeiro elemento

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
 NO *pno, *p;
 int i;

 // procura o ponto a inserir
 for (i = 0, p = &inicio;
      (i <>prox != NULL); i++)
 {
   p = p->prox;
 }
 if (i != pos)
   return FALSE;  // posicao invalida

 // Insere
 pno = malloc (sizeof (NO));
 if (pno == NULL)
   return FALSE;  // faltou memoria
 pno->valor = valor;
 pno->prox = p->prox;
 pno->ant = p;
 if (p->prox != NULL)
   p->prox->ant = pno;
 p->prox = pno;

 return TRUE; // sucesso
}