INSTITUTO SUPERIOR PRIVADO DE ANGOLA

ESTRUTURAS DE DADOS

 

 DISCIPLINA:  Estrutura de Dados

 PROFESSOR: Samuel Kakumba N’gunga

 

Implementação das listas

(II.2) – Listas Vinculadas (Dupla– Circular)

 

1. Características e Estrutura:

A lista   vinculada dupla- circular  herda todas as caracteristicas das listas vinculadas simples circular e com as seguintes propriedades adicionais:

·        Cada elemento da lista possui dois apontadores. Um que aponta para o sucessor e outro para o antecessor, sendo deste modo fácil   o processo de navegação em dois sentidos.

                 

  |     ß   | apontador para antecessor

 | Informação| informação

 |  à            |  apontador para sucessor

Exemplos considere a lista composta pelos nomes Luanda, Namibe:

(Faça clique aqui para ver a Ilustração)

 

 

2. Declaração:

   

   TYPE

          tElemento                                       =…;  {Defina neste espaço o tipo de dados para a lista}                                    

       tLista                                              = ^VinculoLista;                                

         VinculoLista                                   =record

                                                                       info : tElemeneto;     {tipo de dados da lista}

                                                                       proximo   :  tLista ;    {aponta para o próximo elemento}
                                                                        anterior   :  tLista ;    {aponta para o antecessor           }

                                                                   end;                                                                  

 

 

3. Operações:

 

 

3.1 Inserir

      3.5.1 Inserir (depois do elemento apontado por Lista)

        function   InserirDepois (elemento :tElemento;Lista :tLista): tLista;

                var  temporaria : tLista;

        begin

             {criar nova variavel temporária}

              New (temporaria);
 

             {inserir o item }

              temporaria^.info := elemento ;
            

               if vazia(Lista) then

                     begin {inserir numa lista vazia }

                           temporaria^.proximo := temporaria;
                           temporaria^.anterior := temporaria;
                           Lista :=temporaria;

                     end

              else     

                   begin {inserir numa lista  não vazia }

                         temporaria^.proximo := Lista^.proximo;

                         Lista^.proximo =temporaria;

                         temporaria^.anterior := Lista;
                         temporaria^.proximo^.anterior :=temporaria;

                   end;

             {atribuir o resultado final  a função}

              Inserir :=Lista;

        end;

     (I).    Inserir na Lista Vazia. Faça clique aqui para ver a Ilustração
 

     (II). Inserir na Lista não Vazia. Faça clique aqui para ver a Ilustração

 

 

 

3.2  Remover

      Remover

        function   Remover (Lista :tLista): tLista;

          {

             assume lista não vazia

          }
              var  p : tLista;

        begin

             if  not vazia(Lista) then

                  begin

                       p := Lista^.proximo;
                       if   p=Lista then {remove o ultimo elemento da lista e retorna a lista vazia}

                           Lista :=Nil

                        else
                            begin
                                Lista^.proximo :=p^.proximo;
                                Lista^.proximo^.anterior :=p^.anterior;
                             end;

                             dispose(p);

                  end;
              Remover :=Lista;

        end;

 

 
 

4. Vantagens e Desvantagens:

      3.1 Vantagens

• É possivel visitar os todos elementos da lista nos dois sentidos.
• É possivel determinar o sucessor e o antecessor de qualquer elemento da lista facilmente.
  
   

 

       3.2 Desvantagens

• Acesso sequencial  aos elementos da lista.