A lista duplamente encadeada funciona pelo mesmo princípio que a lista encadeada. No entanto, cada nó contém uma referência ao nó anterior e ao próximo, se esse nó estiver disponível. Isso é particularmente útil quando é necessário viajar para trás e para frente.
Nossa lista Duplamente Encadeada será o desafio final e o mais longo com 9 métodos adicionais:
DisplayAllBackwards() DisplayAt(index), AddFirst(data),AddLast(data), Add(data, index), RemoveFirst(), RemoveFirst(), RemoveAt().
DisplayAll():
Descrição:
Retorna um array com os dados, ou se está vazio, retorna null.
this.DisplayAll = function() {
// Na maioria das vezes, head não será nulo, então vamos começar com isso agora
if (head) {
let arr = new Array();
let atual = head;
for (let i = 0; i < contador; i++) {
arr[i] = atual.dado;
atual = atual.proximo;
}
return arr;
} else {
return null;
}
}
DisplayAllBackwards():
Descrição:
Retorna um array com os dados do tail ao head ou, se vazio, retorna nulo. Dê uma olhada neste método e pense em como seria difícil implementá-lo em uma lista encadeada simples.
this.DisplayAllBackwards = function() {
if (head) {
let arr = new Array();
let atual = tail;
for (let i = 0; i < contador; i++) {
arr[i] = atual.dado;
atual = atual.anterior;
}
return arr;
} else {
return null;
}
}
DisplayAt():
Descrição:
Funciona da mesma forma de uma lista encadeada simples.
this.DisplayAt = function(index) {
// verifica valores fora dos limites
if (index > -1 && index < contador) {
let atual = head;
let i = 0;
// não fui eu, é da nczonline (veja fonte).
// É uma maneira diferente de implementar o FOR que estamos usando
// e queria que todos tivessem a chance de conhecê-lo.
while (i++ < index) {
atual = atual.proximo;
}
return atual.dado;
} else {
return null;
}
}
AddFirst():
Descrição:
Adiciona no início da lista duplamente encadeada.
this.AddFirst = function(dado) {
// Cria um novo nó
let node = new Node(dado);
node.proximo = head;
head = node;
//Se a lista está vazia
if (contador === 0) {
tail = head;
} else {
//Não se esqueça do nó anterior. Ele precisa ser referenciado
head.proximo.anterior = head;
}
contador++;
}
AddLast():
Descrição:
Adiciona ao final da lista duplamente encadeada.
this.AddLast = function(dado) {
let node = new Node(dado);
node.anterior = tail;
if (contador === 0) {
head = node;
} else {
tail.proximo = node;
}
tail = node;
contador++;
}
Add():
Descrição:
Adiciona um item em uma posição específica. Dica: desenhe o processo se necessário. Não é tão simples quanto você imagina.
this.Add = function(dado, index) {
// verifica valores fora dos limites
if (index > 0 && index < contador) {
let node = new Node(dado);
let atual = head;
let i = 0;
// encontre o local certo
while (i++ < index) {
atual = atual.proximo;
}
atual.anterior.proximo = node;
node.proximo = atual;
node.anterior = atual.anterior;
atual.anterior = node;
contador++;
} else if (index < 1) {
this.AddFirst(dado);
} else {
this.AddLast(dado);
}
}
RemoveFirst():
Descrição:
Remove o primeiro item.
this.RemoveFirst = function() {
if (head) {
head = head.proximo;
contador--;
//Se há apenas um item
if (contador === 0) {
tail = null;
} else {
// Não se esqueça do nó anterior. Ele também precisa que o conjunto de referência seja nulo.
head.anterior = null;
}
}
}
RemoveLast():
Descrição:
Remove o último item.
this.RemoveLast = function() {
if (head) {
// existe apenas um item
if (contador === 1) {
head = null;
tail = null;
} else {
tail.anterior.proximo = null;
tail = tail.anterior;
}
contador--;
}
}
RemoveAt():
Descrição:
Remove um item de uma posição específica.
this.RemoveAt = function(index) {
// verifica valores fora dos limites
if (index > 0 && index < contador - 1) {
let atual = head;
let i = 0;
// encontre o local certo
while (i++ < index) {
atual = atual.proximo;
}
atual.anterior.proximo = atual.proximo;
atual.proximo.anterior = atual.anterior;
contador--;
} else if (index < 1) {
this.RemoveFirst();
} else {
this.RemoveLast();
}
}
- DISPLAYALL():
- DISPLAYALLBACKWARDS():
- DISPLAYAT(INDICE):
- ADDFIRST(DADO):
- ADDLAST(DADO):
- ADD(DADO,INDICE):
- REMOVEFIRST():
- REMOVELAST():
- REMOVEAT(INDICE):
