Estrutura de Dados com JavaScript: Lista Duplamente Encadeada

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):