Lista Circular, cabeça de lista, lista duplamente ligada

Sétima aula de Estrutura de dados

Mac2301 - primeiro semestre de 2002


Listas circulares ligadas


Uma lista circular ligada tem a propriedade que o último nó aponta
sempre para o primeiro nó. Então de qualquer nó da lista pode-se
atingir qualquer outro nó da lista.



                                    lista
                                      |
                                      V 
            _ _     _ _     _ _     _ _
       +-> |_|_|-> |_|_|-> |_|_|-> |_|_|----+
       |                                    |
       +------------------------------------+



ou lista com um só nó


                                    lista
                                      |
                                      V 
                                    _ _
                                +->|_|_|----+
                                |           |
                                +-----------+



funções para a manipulação de listas circulares:


ApontoNo apont;


void InicializaListaCircular(){
  apont = NULL;
}

// item Inserção à esquerda:
void InsereEsquerda(TipoInfo x){
  ApontNo p;
  ExtraiNo(&p);
  p->info = x;
  if (apont==NULL){  /* Lista vazia */
     p->prox = p;
     apont = p;
  } 
  else {
     p->prox = apont->prox;
     apont->prox = p;
  }  
}

// Inserção à direita:
void InsereDireita(TipoInfo x){
  InsereEsquerda(x);
  apont = apont->prox;
}


// Remoção à esquerda:
void RemoveEsquerda(TipoInfo *x){
  ApontNo p;
  if (apont == NULL)
     Underflow();
  else {
     p = apont->prox;
     *x = p->info;
     if (apont==p) /* Lista com apenas um nó */
        apont = NULL;
     else
        apont->prox = p->prox;
     DevolveNo(p);
  }
}


Observações:

1) Remoções à direita não são eficientes;
2) Uma lista circular pode ser usada como algumas estruturas já
  vistas, considerando: 
   a) Inserir à esquerda;
   b) Inserir à direita;
   c)  Remover à esquerda.


* pilha: combinando (a) e (c);
* fila: combinando (b) e (c);
* fila dupla com saída restrita: combinando (a), (b) e (c).


Operações mais eficientes com lista circular

//Devolver uma lista inteira para a lista livre
ApontNo p;

if (apont != NULL){
   p = apont->prox;
   apont->prox = livre;
   livre = p;
   apont = NULL;
}


//Concatenar duas listas circulares ligadas


Como concatenar as listas apont1 e apont2 na lista apont ?


ApontNo p;

if (apont2 == NULL)
   apont = apont1;
else {
   if (apont1 != NULL){
      p = apont1->prox;
      apont1->prox = apont2->prox;
      apont2->prox = p;
   }
   apont = apont2;
}


Nó cabeça de lista (head of the list)


Nó cabeça de lista é um nó utilizado para indicar o início e o fim de
uma lista circular, e armazena no campo info um valor especial, que
não é um ``valor válido'' para os outros nós da lista.



                                    lista
                                      |
                                      V 
            _ _     _ _     _ _     _ _
       +-> |_|_|-> |_|_|-> |_|_|-> |_|X|----+
       |                                    |
       +------------------------------------+



ou lista vazia


                                    lista
                                      |
                                      V 
                                    _ _
                                +->|_|X|----+
                                |           |
                                +-----------+


Aplicações de listas circulares com ``cabeça'' de lista


Representação de um polinômio. Cada nó tem o formato Cada nó tem o formato:

___________________________
|coeficiente|expoente|  --|-->
---------------------------

e os nós estão ligados em ordem crescente de expoente.

Exemplo: p(x)= 7x^{10}+5x^2+4

     +------------------------------------------------------------+
     v                                                            |
-------------    -------------    -------------    -------------  | 
| 0 | -1 | -|--> | 4 | 0  | -|--> | 5 |  2 | -|--> | 7 | 10 | -|--+ 
-------------    -------------    -------------    -------------    



Representação de inteiros positivos arbitrariamente grandes.


Uma idéia é armazenar os dígitos da direita para a esquerda numa lista
circular ligada, de modo que o primeiro nó contenha o dígito menos
significativo e o último nó contenha o dígito mais significativo.

Ex: O número 12345678901234 é representado por:

            _ __     _ ____     _ ____     _ ____     _ __
 lista +-> |_|-1|-> |_|1234|-> |_|7890|-> |_|3456|-> |_|12|----+
       |                                                       |
       +-------------------------------------------------------+



Listas duplamente ligadas


Cada nó tem o formato:

   -------------------    
 <-|eprox|info|dprox>|->
   ------------------- 

onde:

 info: contém a informação;
 eprox: armazena o endereço do nó predecessor;
 dprox: armazena o endereço do nó sucessor.


Um pouco de código


typedef struct no1 {
          TipoInfo info;
          struct no1  *eprox, *dprox;
        } No, *ApontNo;
ApontNo E, D;



void InicializaListaDupla(){
  E = D = NULL;
}


void InsereDireita(TipoInfo x){
  ApontNo p;
  ExtraiNo(&p);
  p->info = x;
  p->dprox = NULL;
  p->eprox = D;
  if (D == NULL) /* lista vazia */
    E = D = p;
  else {
    D->prox = p;
    D = p;
  }
}


void RemoveEsquerda(TipoInfo *x){
  ApontNo p;
  if (E == NULL)
     Underflow();
  else {
    p = E;
    *x = p->info;
    E = E->dprox;
    if (E == NULL) /* lista ficou vazia */
      D = NULL;
    else
      E ->eprox = NULL;
    DevolveNo(p);
   }
}


Observações

1) Podemos ter variações como a lista circular duplamente ligada;
  - lista dupla circular
  - lista dupla circular com cabeça de lista;

2) Numa lista circular duplamente ligada, todo o nó  p,
  inclusive o cabeça de lista satisfaz: dprox(eprox(p)) = eprox(dprox(p)) = p;

3) Listas duplamente ligadas requerem um espaço adicional para as
   ligações, mas alguma operações tornam-se mais eficientes. Por
   exemplo, remover um nó apontado por p.

/* esta funcao supoe uma lista circular duplamente ligada com cabeca
   de lista, e p diferente do no cabeca */
void RemoveNo (ApontNo p, TipoInfo *x){
   *x = p->info;
   (p->eprox)->dprox = p->dprox;
   (p->dprox)->eprox = p->eprox;
   DevolveNo(p);
}