Este repositório consiste num resumo sobre principais estruturas de dados e algoritmos, implementados na linguagem de programação JavaScript.
O conteúdo aqui presente foi cotejado de diversas fontes e tem objetivo apenas educacional.
Objectos, na linguagem JavaScript, são criados por uma função construtora que inclui declarações para os atributos e métodos do objeto, por exemplo:
function Account(amount) {
this.balance = amount; // atributo
this.deposit = deposit; // método
this.withdraw = withdraw; // método
this.toString = toString; // método
}
function deposit(amount) {
this.balance += amount;
}
function withdraw(amount) {
if (amount <= this.balance) {
this.balance -= amount;
}
if (amount > this.balance) {
console.log('Insufficient funds');
}
}
function toString() {
return 'Balance: ' + this.balance;
}
var account = new Account(100); // objeto criadoA palavra this (this keyword) é usada para criar o laço entre métodos/atributos e os objetos criados a partir da função construtora Account.
Por "baixo dos panos", usar o operador {} para criar um novo objeto, é o mesmo que criar uma função contrutora e chamá-la logo em seguida para gerar um objeto.
Numa das atualizações recentes da linguagem, foram implementadas classes. Assim, a mesma função construtora Account pode ser implementada desta forma:
class Account {
constructor(amount) {
this.balance = amount;
}
deposit(value) {
this.balance = value;
}
withdraw(value) {
if (this.balance >= value) this.balance -= value;
}
toString() {
return `Balance: ${this.balance}`;
}
}
const account = new Account(100);Classes, portanto, são moldes (ou templates) de objetos.
Uma famoso ditato popular dev diz:
"Para entender recursividade, é preciso primeiro entender recursividade." - Autor desconhecido
Recursividade é um método usado para resolução de problemas. O método consiste em resolver pequenas porções do problema repetidamente, até que todo o problema seja resolvido.
Um método ou função é recursivo se pode chamar-se a si mesmo:
function recursive(param) {
recursive(param);
}Um função também é considerada recursiva se ela pode chamar-se indiretamente:
function recursive(param) {
recursive2(param);
}
function recursive2(param) {
recursive(param);
}Se de fato chamássemos a função recursive, ela seria executada indefinidamente. Por essa razão, todas as funções desse tipo deve ser condicionadas (a condição chama-se base case) para prevenir recursão infinita.
Seguem alguns exemplos comuns de funções recursivas.
O fatorial de 5 é representado por 5! e é igual a 5 * 4 * 3 * 2 * 1.
A representação dos passos necessários para computar o fatorial de um número n é: n * (n - 1) * (n - 2) * (n - 3) * ... * 1
Usando loop (método iterativo), poderíamos escrever a seguinte função para calcular o fatorial de n:
function factorialIterative(number) {
// Se 'number' é negativo retorna 'undefined'
if (number < 0) return undefined;
let total = 1;
for (let n = number; n > 1; n--) {
total *= n;
}
return total;
}Usando recursividade poderíamos escrever a seguinte função para resolver o mesmo problem:
function factorial(n) {
// Condição de parada (base case):
if (n === 1 || n === 0) return 1;
//Recursão:
return n * factorial(n - 1);
}A sequência Fibonacci pode ser gerada através de recursividade. A sequência é 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.... A série pode ser definida desta forma:
- O primeiro elemento (índice 0) é
0; - Os elementos nas duas posições seguintes (índices 1 e 2) são
1; - O elemento na posição
n, paran > 2, é igual ao valor da śerie na posiçãon - 1+ o valor na posiçãon -2.
function fibonacciInteractive(n) {
if (n < 1) return 0;
if (n <= 2) return 2;
let fibNMinus2 = 0; // Valor da série em 'n - 2'
let fibNMinus1 = 1; // Valor da série em 'n - 1'
let fibN = n;
for (let i = 2; i <= n; i++) {
fibN = fibNMinus1 + fibNMinus2;
fibNMinus2 = fibNminus1;
fibNminus1 = fibN;
}
return fibN;
}function fibonacci(n) {
if (n < 1) return 0;
if (n <= 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}Diagrama com as chamadas da função fibonacci:
Há, ainda, um terceiro método, chamado memoization, de calcular a sequência. Memoization é uma técnica de otimização com a qual valores computados anteriormente são memorizados, similarmente a um cache.
Se analizarmos as chamadas realizadas da função fibonacci para computar fibonacci(5), notaremos que fibonacci(3) é computado 2 vezes. Podemos, portanto, armazenar esse resultado já computado para que, quando necessário, já tenhamos o valor disponível.
Função fibonacci com memoization:
function fibonacciMemoization(n) {
const memo = [0, 1];
const fibonacci = (pos) => {
if (memo[pos] !== undefined) return memo[pos];
return (memo[pos] = fibonacci(pos - 1) + fibonacci(pos - 2));
};
return fibonacci(n);
}O array memo faz o cache de todos os valores computados. Na arrow function fibonacci, se o valor Fibonacci de n já foi computado, este valor é retornado; caso contrário, o valor é calculado e adicionado ao cache.
Call stack é o mecanismo usado por um interpretador (como o interpretador de JavaScript no browser) para saber em que ponto de um script, em que pode haver múltiplas chamadas de funções, ele está; ou seja, o call stack serve para o interpretador saber que função está sendo executada e quais outras são chamadas desde dentro dessa função.
- Quando um script chama uma função, o interpretador a adiciona ao call stack e passa a executar a função.
- Quaisquer funções chamadas pela primeira são empilhadas na call stack e executadas
- Quando a função atualmente em execução é finalizada, o interpretador a remove da pilha e retorna a execução do script de onde havia parado, conforme sequência de chamadas na call stack
Se adicionarmos console.trace() à função factorial e a executarmos no navegador, veremos o seguinte resultado:
Ou seja, a função factorial é chamada 3 vezes durante a operação. Podemos ainda representar os passos executados e as ações na call stack com o seguinte diagrama:
Se, numa chamada recursiva, esquecermos de adicionar uma condição de parada, o navegador lançará o erro stack overflow error.
Cada engine tem sua limitação. Podemos testar o limite do Google Chrome, por exemplo, com o seguinte código:
ES6 introduziu tail call optimization, ou seja, se a chamada de uma função é a última ação dentro de uma função, a engine otimiza essa execução e não a adiciona à call stack. Na prática, isso significa que uma chamada recursiva pode ser executada indefinidamente em ECMAScript 2015.
Listas são especialmente úteis se não temos de fazer pesquisas pelos itens ou ordená-los de alguma forma. Como as estruturas de dados serão criadas aqui com objetos, devemos definir os atributos (características) e métodos (ações) da classe List.
- Lista é uma sequência ordenada de dados
- Cada item da lista é chamado elemento. Em JavaScript, elementos podem ser de qualquer tipo (string, number, boolean etc).
- O tamanho da lista não é pre-determinado
- Uma lista sem elementos é empty
- O número de elementos da lista é chamado length
- O número de elementos é guardado internamente na propriedade listSize
- Podemos acrescentar (append) um elemento ao final da lista
- Podemos inserir (insert) um elemento no começo ou em qualquer posição da lista
- Elementos são excluídos através de um método remove
- Há um método para limpar a lista (clear)
- Os elementos são mostrados através do método toString() ou getElement()
- Listas tem propriedades para descrever posição
- O começo da lista é o front
- O término da lista é o end
- Podemos iterar pelos elementos da lista através de um método next() ou prev()
- Podemos acessar um elemento específico através de um método moveTo(n), em que n especifica a posição
- A propriedade curPos indica a posição atual
- A especificalçao abstrata de lista não define uma função de armazenamento. Nesta implementação será usado um array chamado dataStore
Clique aqui para ver a implementação da lista.
Stack (pilha) é uma lista de elementos acessíveis somente desde um ponto da lista, o qual é chamado topo. A stack é conhecida como last-in, first-out (LIFO) - último a chegar, primeiro a sair.
Para pegar um elemento do fundo da stack, todos os outros elementos devem ser removidos primeiro.
- Elementos são adicionados através da operação push
- Elementos são removidos através da operação pop
- A operação peek retorna o valor do topo da lista, sem removê-lo
- A propriedade top é incrementada a cada push e subtraída a cada pop
- A operação clear remove todos os elementos da pilha
- A propriedade length guarda o número de elementos da pilha
- A propriedade empty (boolean) indica se a pilha está vazia
Clique aqui para ver exemplos de uso e a implementação da stack.
Filas (queues) são um tipo de lista em que os dados são inseridos no fim e removidos do início. Filas são usadas para armazenar dados na ordem de ocorrência, ao contrário das pilhas (stacks), em que o último dado inserido é o primeiro a ser processado.
Filas são exemplos de estrutura de dados first-in, first-out (FIFO) - primeiro a chegar, primeiro a sair. Filas são usadas para ordenar processos submetidos, por exemplo, a um sistema operacional, impressoras etc.
As duas principais operações de queues são inserção e remoção de elementos. A inserção é chamada enqueue (enfileirar), e a remoção dequeue. A operação enqueue insere um novo elemento no fim da fila; a operação dequeue remove um elemento da frente da fila.
A operação de checar o primeiro elemento da fila chama-se peek. Essa operação retorna o elemento da frente da fila sem removê-lo. Filas também têm a propriedade length - ou o método size -, que guarda/retorna a quantidade de elementos da fila. Por fim, a operação clear remove todos os elementos da queue.
Clique aqui para ver a implementação, exemplos e exercícios relacionados a filas
A estrutura de dados deque (double ended queue), também conhecida como double-ended queue, é um tipo especial de fila que permite inserir e remover elementos do fim e do início dela.
Uma aplicação comum de deques é armazenar uma lista de operações desfeitas (undo operations). Cada vez que um usuário realiza uma operação no software, a operação é guardada numa deque. Quando o usuário clica num botão "desfazer", a opearção é removida da deque - ou seja, a operação do fim é removida (assim como uma stack). Depois de uma quantidade pre-definida de operações, os dados mais antigos da deque são removidos da frente da deque (assim como uma queue). Porque esta estrutura de dados implementa os princípios FIFO e LIFO, podemos dizer que deques são uma mescla entre filas e pilhas.
Clique aqui para ver a implementação de deques
Arrays não são a melhor estrutura de dados em algumas situações. Em muitas linguagens de programação, arrays tem tamanho fixo, tornando trabalhosa a adição de elementos quando o tamanho máximo é alcançado. Além disso, nessas mesmas linguagens, adicionar e remover elementos de um array significa ter de realocar o índice de todos os outros elementos. Essas dificuldades, porém, não existem em JavaScript - podemos usar shift() ou split() sem a preocupação de acessar outros elementos do array.
O principal problema de arrays em JavaScript, no entanto, é eles serem implementados como objetos, tornando-os menos eficientes que arrays construídos em outras linguagem (C++ e Java, por exemplo).
Um array é uma alocação linear (contígua) de memória em que elementos são acessados por números inteiros. Esses inteiros, por sua vez, são usados para computar offsets (deslocamentos), ou seja, cada inteiro é um índice de um espaço da memória alocada para o array. JavaScript não possui nada parecido com isso.
Para entender melhor arrays, vamos supor a criação de um, na lingugem de programação Java. Para criar um array em Java podemos fazer o seguinte:
int[] arr = {0, 1, 2, 3}; // criamos uma array de inteirosCom essa linha de código, criamos um array estático contendo 4 números inteiros. O compilador vê esse código e entende que precisamos de um array de inteiros, e que ele precisa requerer memória para isso. Cada número do tipo int ocupa 4 bytes de memória, portanto são necesários 16 bytes para aquele array.
A memória dos computadores é organizada em células, cada qual é capaz de armazenar 8 bits e possui um índice numérico. Um byte é igual a 8 bits, portanto o array acima necessita de 16 células de memória (128 bits).
O problema para adicionar novos dados em arrays é que não escolhemos quais células serão usadas para guardá-lo, muito menos podemos gerenciar as células vizinhas. Não podemos, portanto, garantir que as células próximas ao array estarão disponíveis. A solução para isso é simplesmente criar um novo array com a quantidade extra de memória, copiar os valores antigos nesse novo array e adicionar os novos dados.
Remover elementos de um array é, mutatis mutandis, o mesmo problema.
Em vez desse tipo de arrays, JavaScript disponibiliza objetos que possuem características de arrays. O primeiro elemento de um array JavaScript tem a propriedade (chave) '0', o segundo a propriedade '1' etc. A diferença entre
const obj = { 0: 'zero', 1: 'um' };e
const arr = ['zero', 'um'];é que o protótipo de obj é Object.prototype, e o de arr é Array.prototype; ou seja, o array arr herda, por exemplo, os métodos push, shift, pop, map; já o objeto obj não tem acesso a nada disso.
Apesar de poder ser mais convenientemente manipulado, um arrray JavaScript é significantemente mais lento que um array de fato.
Quando operações com arrays tornam-se lentas demais, podemos considerar listas encadeadas como um alternativa. Essas listas pode ser usadas em quase todas as situações em que arrays unidimensionais são usados, exceto se for preciso acesso a elementos aleatórios da lista; nesse caso, arrays devem ser usados.
Listas encadeadas são uma coleção de nodes (nódulos). Cada nódulo é ligado ao seu sucessor por meio de uma referência. A referência a outro node é chamada link.
Apesar de serem, assim como arrays, uma coleção sequencial de elementos, os elementos das linked lists não são alocados em lugares contíguos da memória.
Enquanto os elementos de um array são referenciados pela sua posição, elementos de uma linked list são referenciados por sua relação ao outros elementos da lista.
Um dos benefícios de uma lista encadeada em relação aos arrays convencionais é não precisarmos deslocar todos os elementos da lista ao adicionarmos ou removermos elementos. Precisamos, porém, usar pointers (ou links) ao trabalharmos com listas encadeadas; se quisermos, por exemplo, acessar um certo elemento do meio da lista, precisaremos necessariamente percorrer a lista do primeiro elemento até o elemento desejado.
Dada a seguinte representação de lista encadeada
'leite' => 'pão' => 'ovos' => 'bacon' => null
dizemos que pão sucede leite, não que pão está na segunda posição.
Mover por uma linked list significa seguir os elos da lista, do começo do nódulo inicial ao último. O fim da lista aponta para um nódulo null.
Muitas implementações de linked lists incluem um tipo especial de node, chamado head, sendo ele o começo da lista.
Para inserir ou remover um elemento da lista, basta redefinir os elos entre os nodes. Por exemplo, para adicionar biscoito depois de ovos, fazemos ovos apontar para biscoito, e este apontar para bacon:
'leite' => 'pão' => 'ovos' => 'biscoito' => 'bacon' => null
Para remover bacon da lista, basta fazer biscoito apontar para null.
Clique aqui para ver a implementação, exemplos de uso e exercícios de listas encadeadas
Um dicionário é usado para guardar pares de chave/valor, podendo a chave ser usada para encontrar o valor. Dicionários são também chamados mapas, tabela de símbolos ou arrays associativos.
Objetos em JavaScript são desenhados para serem operados como dicionários. Além disso, a partir de ECMAScript 2015, outras implementaççoes de dicionários foram adicionadas à linguagem: as classes Map, WeakMap e WeakSet.
Mais sobre Map, WeakMap e WeakSet aqui
Set é uma coleção de dados desordenados e únicos (valores não podem se repetir). Esta estrutura de dados usa o conceito metemático de conjuntos finitos aplicado a uma estrutura de dados computacional.
Em matemática, um conjunto (ou set) é uma coleção de objetos distintos. Por exemplo, o conjunto dos números naturais é a coleção de números inteiros positivos N = {0, 1, 2, 3...}.
Conjuntos matemáticos possuem, ainda, algumas operações básicas: união, intercessão e diferença. A estrutura de dados set também possui essas características.
Podemos iniciar uma classe Set desta forma:
class Set {
constructor() {
this.items = {};
}
}Precisamos então declarar os métodos disponíveis para um set:
add(element): Adiciona um novo elemento ao set;delete(element): Apaga um novo elemento do set;has(element): Retornatrueseelementexiste no conjunto efalsose não existir;clear(): Remove todos os elementos do conjunto;size(): Retorna o número de elementos do conjunto;values(): Retorna um array com todos os valores (elements) do conjunto;
Hash table (tabela hash, ou tabela de espelhamento) é um tipo de dicionário.
Enquanto outras estruturas têm de iterar seus elementos para encontrar um valor específico, a hash table é capaz de retornar diretamente o valor, dada certa chave, sem necessidade de iterar por seus elementos.
Hash tables possibilitam muita rapidez para inserção, exclusão e extração de dados, porém têm baixa performance em operações que envolvem buscas (como achar o valor mínimo e máximo de um conjunto de dados) - para buscas, estruturas como binary search tree são mais adequadas.
São salvos numa hash table dados em pares key/value. Cada key é associada a um hash, que por sua vez é criado com uma função hash.
As tabelas de dispersão têm muitos casos de uso. Podem ser usadas, por exemplo, para indexar tabelas de um banco de dados e extrair dados mais rapidamente. Outro uso comum dessa estrutura é a representação de objetos: a linguagem JavaScript usa internamente hash table para representar os objetos; assim, cada propriedade ou método do objeto é representado como uma key, e as keys apontam para o seu respectivo membro no objeto.
A função hash que iremos implementar a seguir chama-se lose-lose hash, em que são somados todos os valores ASCII dos caracteres das chaves. A figura abaixo ilustra o conceito de hashing e o uso da função hash:
Clique aqui para ver a implementação, exemplos de uso e exercícios de hash tables