Lista duplamente ligada

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na área de engenharia de software, uma lista duplamente ligada (ou lista duplamente encadeada) é uma extensão da lista simplesmente ligada (ou lista simplesmente encadeada).

Numa lista cada elemento, ou nó, é composto normalmente por uma variável que guarda a informação(Objeto, inteiro, cadeia de caractéres, etc) e dois ponteiros (referências a endereços de memória) que permitem a ligação entre os vários nós desta lista. Este tipo de lista é conhecido por "Duplamente ligada" ou "Duplamente encadeada" exatamente pelo fato de possuir duas váriaveis de controle (ponteiros) ao contrário da lista simplesmente ligada que possui somente um, o qual aponta para o próximo elemento da lista.

A função destas variáveis é guardar o endereço de memória do nó anterior e do nó posterior, identificados normalmente como "prev" ou "previous" e "next". Com estas estruturas podemos realizar diversas tarefas que seriam impossiveis ou muito dispendiosas com uma lista simplesmente encadeada.

No modelo mais simples deste tipo de lista, ao criar a lista o primeiro nó tem seu ponteiro "previous" apontando sempre para nulo e o último nó com seu "next" apontando para nulo.

Existem várias ramificações da lista duplamente encadeada, e muitas delas servem também para a lista simplesmente encadeada. Aqui temos alguns exemplos:

  • Lista duplamente encadeada com sentinelas: Neste modelo de lista possuimos dois Nós estáticos a cabeça da lista (head) e o fim da lista(tail). O elemento prev (anterior) do nó head aponta sempre para nulo enquanto no nó tail quem aponta para nulo é o next(próximo).

Vantagens: Maior facilidade de controle da lista, maior confiabilidade e menor risco de perda acidental da lista.

Desvantagens: Maior gasto de espaço em disco (2 nós a mais).

  • Lista duplamente encadeada circular: Neste modelo de lista possuimos apenas um sentinela. Esta lista é conhecida como circular pois o sentinela aponta para o primeiro elemento da lista e o último elemento da lista aponta para o sentinela, formando assim um círculo lógico.

Vantagens: Economia de espaço em disco (1 nó a menos que a lista duplamente encadeada com sentinelas), maior confiabilidade em relação ao modelo comum.

Desvantagens: Maior complexidade nos algoritmos.

Exemplo de Lista Duplamente Ligada em C[editar | editar código-fonte]

Estrutura


// lista simples... sem a o nó cabeça...
typedef struct lista_int{
   int numero;
   struct lista_int *seg;
   struct lista_int *ant;
}lista_dupla;

Exemplo de Lista Duplamente Ligada em Java[editar | editar código-fonte]

Estrutura


class DLNode{
   private Object element;
   DLNode next;
   DLNode prev;
   public DLNode(Object element, DLNode prev, DLNode next){
      this.element=element;
      this.prev=prev;
      this.next=next;
   }
   public void setElement(Object element){
      this.element=element;
   }
   public void setNext(DLNode next){
       this.next=next;
   }
   public void setPrev(DLNode prev){
      this.prev=prev;
   }
   public Object getElement(){
      return element;
   }
   public DLNode getPrev(){
      return prev;
   }
   public DLNode getNext(){
      return next;
   }
}