Tag: Programação

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!

Uma lista encadeada é uma sequência de objetos, onde cada elemento da sequência é armazenado em uma célula (nó) desta lista. O primeiro fica na primeira célula, o segundo na segunda célula e assim, sucessivamente. Cada célula possui seu próprio conteúdo. Você vai perceber as semelhanças entre Lista Encadeada, Fila e Pilha, visto que estas duas últimas foram criadas usando a ideia básica da Lista Encadeada. Seguindo nossa sequência, criaremos esta estrutura usando CLASS. Vamos definir nossa Lista Encadeada. Ela precisará de um Head para iniciar a lista e também um contador:

class ListaEncadeada{
    constructor(head = null, count = 0){
        this.head = head;
        this.count = count;
    }

    GetContador(){
        return this.count;
    }
}

Nossa lista terá os seguintes métodos:

• MostrarTudo();
• MostrarEm(index);
• AdicionarInicio(data);
• AdicionarNaPosicao(data, index);
• RemoverInicio();
• RemoverNaPosicao(index).

Vamos lá!

MostrarTudo():

Como o próprio nome já diz, esse método mostra todos os elementos que estão na lista. Ele retornará um array contendo os dados e, se a lista estiver vazia, retorna null:

MostrarTudo(){
    if (this.head === null){
        return null;
    } else {
        let arr = [];
        let current = this.head;

        for (let i = 0; i < this.count; i++) {
            arr[i] = current.data;
            current = current.next;
        }
        return arr;
    }
}

MostrarEm(index):

Nosso método MostrarEm nos retorna o elemento que está na posição desejada (index). Caso a posição buscada seja inexistente, o método retornará null:

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

O nosso método adicionará o dado no início da lista. Caso esteja se perguntando, o início da lista é onde o índice é 0 e é referenciado pelo head. Precisamos incrementar o contador ao realizar a inserção:

AdicionarInicio(data){
    let no = {
        data: data,
        next: this.head
    };

    this.head = no;
    this.count++;
}

AdicionarNaPosicao(data, index):

Adiciona um item na posição determinada. Precisamos verificar se não está fora dos limites da nossa lista encadeada. Caso não exista essa posição, mostraremos uma mensagem no console:

AdicionarNaPosicao(data, index){
    if (index === 0) {
        this.AdicionarInicio(data);
    } else if (index > -1 && index < this.count){
        let no = {
            data: data,
            next: null
        };

        let previous;
        let current = this.head;
        let i = 0;

        while (i++ < index){
            previous = current;
            current = current.next;
        }

        previous.next = no;
        no.next = current;

        this.count++;
    } else {
        console.log("Não existe esta posição na lista.")
    }
}

RemoverInicio():

O método RemoverInicio() remove o primeiro item da lista. Caso a lista esteja vazia, o método retorna null.

RemoverInicio(){
    if (this.head === null){
        return null;
    } else {
        let out = this.head;
        this.head = this.head.next;

        if (this.count > 0){
            this.count--;
        }

        return out.data;
    }
}

RemoverNaPosicao(index):

Remove o item que está na posição especificada. Precisamos novamente verificar se o índice está dentro dos limites da nossa lista:

RemoverNaPosicao(index){
    if (index === 0) {
        return this.RemoverInicio(this);
    } 
        
    else if ( index > -1 && index < this.count){
            
        let current = this.head;
        let previous;
        let i = 0;

        while (i++ < index){
            previous = current;
            current = current.next;
        }

        previous.next = current.next;
        this.count--;

        return current.data;
    } else {
        return null;
    }    
}

Gostou deste artigo? Comente abaixo!