Estrutura de Dados e Classes JavaScript: Lista Duplamente Encadeada

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!