Lista duplamente ligada
Em ciência da computação, uma lista duplamente ligada (ou lista duplamente encadeada) é uma estrutura de dados ligada que consiste de um conjunto de registros sequencialmente ligados chamados de nós e é uma extensão da lista simplesmente ligada (ou lista simplesmente encadeada). Cada nó contem dois campos, chamados de links ou enlaces, que são referências para o nó anterior e para o nó posterior na sequência de nós. Os links anteriores e posteriores dos nós inicial e final, respectivamente, apontam para algum tipo de terminador, tipicamente um nó sentinela ou nulo, para facilitar o percorrimento da lista. Se houver apenas um nó sentinela, a lista será vinculada circularmente através do nó sentinela. Ele pode ser conceituado como duas listas unicamente vinculadas formadas a partir dos mesmos itens de dados, mas em ordens sequenciais opostas.
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. Este modelo não é muito confiável, já que não há um controle efetivo para saber quem é o primeiro e quem é o ultimo elemento, já que a única maneira de extrair tal informação é verificar quem possui o "prev" ou o "next" 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 Node {
private Object element;
Node next;
Node prev;
public Node(Object element, Node prev, Node next) {
this.element = element;
this.prev = prev;
this.next = next;
}
public void setElement(Object element) {
this.element = element;
}
public void setNext(Node next) {
this.next = next;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Object getElement() {
return element;
}
public Node getPrev() {
return prev;
}
public Node getNext() {
return next;
}
}