Lista Encadeada Simples

[download id=”580″]

Neste artigo será abordada apenas uma estrutura de dados, a lista simples, pois a mesma já possui um grau de dificuldades um pouco mais alto que a pilha e a lista. O código fonte JavaScript será deixado disponível e uma breve explicação junto com o uso mais comum desta estrutura.

Conceito Básico

A lista simples, também conhecido como lista encadeada simples ou lista de um caminho é um tipo básico de estrutura de dados que tem por foco a flexibilidade no manuseio das informações nela contida.

Ela é disposta por nós (Nodes) que se conectam a no máximo 1 outro nó e não possuem conhecimento se um nó é ligado a eles. A forma mais simples de pensar na lista seria um número X de caixas colocadas em fila e cada uma contem duas informações: O dado (informação) e a referência (código) para a próxima caixa.

Ao contrario das estruturas de dados apresentadas no artigo https://mundojs.com.br/2018/02/05/pilhas-e-filas/, a lista é bem mais flexível e permite que novos itens sejam adicionados em qualquer local. Quando isso acontece, ocorrerá o nó anterior e o que está naquela posição terão que ser ajustados conforme a imagem:

Remover de qualquer lugar da lista também é possível e, da mesma forma que o método de adicionar, será necessário ajustar os nós anteriores e posteriores de acordo.

Apesar de possuir uma implementação um pouco mais complexa, comparado com a fila e a pilha, a lista é uma estrutura extremamente útil que já possui implementação em diversas linguagens de programação (Java, C#, Python, etc…) pois ao contrario do vetor, tem um número indefinido de registro que podem ser conectados e acessados de forma ordenada.

Código Fonte

function ListaSimples() {
    var quantidade = 0;
    var primeiro = null;

    //Retorna a quantidade de itens na lista
    this.GetQuantidade = function() {
        return quantidade;
    }

    //Exibe todos os itens da lista no formato de vetor javascript
    this.ExibirTodos = function() {
        if (primeiro === null) {
            return null;
        } else {
            var arr = new Array();
            var atual = primeiro;
            for (var i = 0; i < quantidade; i++) {
                arr[i] = atual.dado;
                atual = atual.prox;
            }
            return arr;
        }
    }
    
    //Exibe o item que está localizado no indice pedido
    this.MostrarNoIndice = function(indice) {
        //Cofere se o indice existe na lista
        if (indice > -1 && indice < quantidade) {
            var atual = primeiro;
            var i = 0;

            while (i++ < indice) {
                atual = atual.prox;
            }

            return atual.dado;
        } else {
            console.log("Indice inválido");
        }
    }
    
    //Adiciona na frente da lista
    this.AdicionarPrimeiro = function(dado) {
        var node = {
            dado : dado,
            prox : primeiro
        };

        primeiro = node;
        quantidade++;
    }
    
    //Adiciona um item em uma posição especifica da lista
    this.Adicionar = function(dado, indice) {
        if (indice === 0) {
            this.AdicionarPrimeiro(dado);
        }
        //Cofere se o indice existe na lista
        else if (indice > -1 && indice < quantidade) {

            var node = {
                dado : dado,
                prox : null
            };

            var anterior;
            var atual = primeiro;
            var i = 0;

            //percorre a lista para adicionar no loca correto
            while (i++ < indice) {
                anterior = atual;
                atual = atual.prox;
            }

            anterior.prox = node;
            node.prox = atual;

            quantidade++;
        } else {
            console.log("Indice inválido");
        }
    }
    
    //Remove o primeiro item da lista
    this.RemverPrimeiro = function() {
        if (primeiro === null) {
            return null;
        } else {
            var sair = primeiro;
            primeiro = primeiro.prox;

            if (quantidade > 0) {
                quantidade--;
            }

            return sair.dado;
        }
    }
    
    //Remove o item na posição especifica do Indice
    this.RemoverNoIndice = function(indice) {

        if (indice === 0) {
            return this.RemverPrimeiro(indice);
        }
        //Cofere se o indice existe na lista
        else if (indice > -1 && indice < quantidade) {

            var atual = primeiro;
            var anterior;
            var i = 0;

            while (i++ < indice) {
                anterior = atual;
                atual = atual.prox;
            }

            //"pula" o item para remove-lo
            anterior.prox = atual.prox;

            quantidade--;
        } else {
            console.log("Indice inválido");
        }

        //Retorna o valor do item removido
        return atual.dado;
    }
}