A Lista Duplamente Encadeada permite que seja percorrida em duas direções, direita e esquerda, diferentemente da Lista Encadeada simples, que permite que seja percorrido em apenas uma direção. Na Lista Duplamente Encadeada, cada elemento possui uma referência para o próximo elemento e para o elemento anterior, se esse elemento estiver disponível. Assim, podemos viajar para trás e para frente de cada elemento da lista.
Para criar nossa Lista, precisaremos de uma classe principal chamada ListaDuplamenteEncadeada e um classe que nos servirá de apoio, evitando reescrever código, chamada Node. A nossa lista terá um contador, que começará em 0 e, também, uma cabeça (head) e uma cauda (tail), que inicialmente terão o valor null:
class ListaDuplamenteEncadeada {
constructor(head = null, tail = null, count = 0){
this.head = head;
this.tail = tail;
this.count = count;
}
}
class Node{
constructor(data, next = null, previous = null){
this.data = data;
this.next = next;
this.previous = previous;
}
}
Precisamos também implementar os métodos getHead, getTail e getCount:
getHead(){
if (this.head) {
return this.head.data;
}
return null;
}
getTail(){
if (this.tail) {
return this.tail.data;
}
return null;
}
GetCount(){
return this.count;
}
A nossa lista terá os seguintes métodos:
- MostrarTudo();
- MostrarFimInicio();
- VisualizarEm(index);
- AdicionarInicio(data);
- AdicionarFinal(data);
- AdicionarEm(data, index);
- RemoverInicio();
- RemoverFinal();
- RemoverEm(index).
Vamos lá!
MostrarTudo():
Como o próprio nome já diz, esse método nos mostrará todo o conteúdo da Lista Duplamente Encadeada. Para isso, utilizaremos um Array que conterá todos os dados da lista e percorreremos esse array com um laço FOR. Caso não ocorra a existência de dados na lista, retornará null:
MostrarTudo(){
if (this.head){
let arr = [];
let current = this.head;
for (let i = 0; i < this.count; i++){
arr[i] = current.data;
current = current.next;
}
return arr;
} else {
return null;
}
}
MostrarFimInicio():
Esse método retorna um array que contém os dados de trás para frente, ou seja, da cauda para a cabeça (tail to head). Caso esteja vazio, retornará null:
MostrarFimInicio(){
if (this.head){
let arr = [];
let current = this.tail;
for (let i = 0; i < this.count; i++){
arr[i] = current.data;
current = current.previous;
}
return arr;
} else {
return null;
}
}
VisualizarEm(index):
Esse método retorna o item no índice indicado. Caso esse índice não exista, retornará null:
VisualizarEm(index){
if (index > -1 && index < this.count){
let current = this.head;
let i = 0;
while (i++ < index){
current = current.next;
}
return current.data;
} else {
return null;
}
}
AdicionarInicio(data):
Adiciona o elemento ao início da lista. Se a lista estiver vazia, o elemento adicionado será o único da lista:
AdicionarInicio(data){
let no = new Node(data);
no.next = this.head;
this.head = no;
if (this.count === 0){
this.tail = this.head;
} else {
this.head.next.previous = this.head;
}
this.count++;
}
AdicionarFinal(data):
Funciona de maneira semelhante ao método anterior, mas adiciona o elemento ao final da lista:
AdicionarFinal(data){
let no = new Node(data);
no.previous = this.tail;
if (this.count === 0){
this.head = no;
} else {
this.tail.next = no;
}
this.tail = no;
this.count++;
}
AdicionarEm(data, index):
Adiciona o elemento no índice indicado:
AdicionarEm(data, index){
if (index > 0 && index < this.count){
let no = new Node(data);
let current = this.head;
let i = 0;
while(i++ < index){
current = current.next;
}
current.previous.next = no;
no.next = current;
no.previous = current.previous;
current.previous = no;
this.count++;
} else if (index < 1){
this.AdicionarInicio(data);
} else {
this.AdicionarFinal(data);
}
}
RemoverInicio():
Remove o elemento situado no início da lista:
RemoverInicio(){
if (this.head){
this.head = this.head.next;
this.count--;
if (this.count === 0){
this.tail = null;
} else {
this.head.previous = null;
}
}
}
RemoverFinal():
Remove o elemento situado no final da fila. Não esqueça de decrementar o contador:
RemoverFinal(){
if(this.head){
if(this.count === 1){
this.head = null;
this.tail = null;
} else {
this.tail.previous.next = null;
this.tail = this.tail.previous;
}
this.count--;
}
}
RemoverEm(index):
Remove o elemento no índice indicado:
RemoverEm(index){
if (index > 0 && index < this.count-1){
let current = this.head;
let i = 0;
while( i++ < index){
current = current.next;
}
current.previous.next = current.next;
current.next.previous = current.previous;
this.count--;
} else if (index < 1){
this.RemoverInicio();
} else {
this.RemoverFinal();
}
}
Teste no seu navegador:
let lista = new ListaDuplamenteEncadeada();
lista.AdicionarInicio(1);
lista.AdicionarInicio(4);
lista.AdicionarInicio(5);
lista.AdicionarInicio(6);
lista.AdicionarFinal(2);
lista.AdicionarEm(3, 1);
console.log(lista.VisualizarEm(1));
console.log(lista.MostrarFimInicio());
lista.RemoverEm(2);
lista.RemoverInicio();
lista.RemoverFinal();
console.log(lista.MostrarTudo());
E a saída será:
Gostou deste artigo? Comente abaixo!
