Algoritmos e Estruturas de Dados em JavaScript: Guia Prático

Algoritmos e Estruturas de Dados em JavaScript: na prática

No desenvolvimento web moderno, o conhecimento de algoritmos e estruturas de dados não é apenas uma habilidade acadêmica, mas uma ferramenta para criar aplicações rápidas e escaláveis. JavaScript, especialmente no ambiente Node.js, permite implementar construções algorítmicas tanto simples quanto complexas. Neste artigo, vamos explorar as principais estruturas de dados e algoritmos na prática, com exemplos de código que podem ser usados imediatamente em projetos.

1. Estruturas de dados básicas: pilha, fila e lista encadeada

Vamos começar pelo fundamento. Pilha e fila são estruturas lineares frequentemente usadas em parsing, filas de tarefas e gerenciamento de histórico de ações.

Pilha (LIFO)

A pilha funciona pelo princípio "último a entrar, primeiro a sair". Vamos implementá-la com base em um array:

class Stack {  constructor() {    this.items = [];  }

  push(element) {    this.items.push(element);  }

  pop() {    return this.items.pop();  }

  peek() {    return this.items[this.items.length - 1];  }

  isEmpty() {    return this.items.length === 0;  }}

// Exemplo de usoconst stack = new Stack();stack.push('Page 1');stack.push('Page 2');console.log(stack.pop()); // 'Page 2'

Fila (FIFO)

A fila é útil para processar tarefas na ordem de chegada. Implementação usando classe:

class Queue {  constructor() {    this.items = {};    this.front = 0;    this.rear = 0;  }

  enqueue(element) {    this.items[this.rear] = element;    this.rear++;  }

  dequeue() {    const item = this.items[this.front];    delete this.items[this.front];    this.front++;    return item;  }

  peek() {    return this.items[this.front];  }

  size() {    return this.rear - this.front;  }}

// Exemploconst queue = new Queue();queue.enqueue('Task 1');queue.enqueue('Task 2');console.log(queue.dequeue()); // 'Task 1'

Lista encadeada

A lista encadeada é eficiente para inserção e remoção de elementos no meio da lista. Vamos implementar uma lista simplesmente encadeada:

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}

class LinkedList {  constructor() {    this.head = null;    this.tail = null;    this.length = 0;  }

  append(value) {    const newNode = new Node(value);    if (!this.head) {      this.head = newNode;      this.tail = newNode;    } else {      this.tail.next = newNode;      this.tail = newNode;    }    this.length++;  }

  prepend(value) {    const newNode = new Node(value);    newNode.next = this.head;    this.head = newNode;    if (!this.tail) {      this.tail = newNode;    }    this.length++;  }

  print() {    const arr = [];    let current = this.head;    while (current) {      arr.push(current.value);      current = current.next;    }    return arr;  }}

// Exemploconst list = new LinkedList();list.append(10);list.append(20);list.prepend(5);console.log(list.print()); // [5, 10, 20]

2. Algoritmos de busca: linear e binária

A busca é uma das operações mais comuns. Vamos considerar duas abordagens: a busca linear simples e a busca binária eficiente.

Busca linear

Adequada para dados não ordenados. Complexidade O(n):

function linearSearch(arr, target) {  for (let i = 0; i < arr.length; i++) {    if (arr[i] === target) {      return i; // Retorna o índice    }  }  return -1;}

console.log(linearSearch([3, 7, 1, 9, 4], 9)); // 3

Busca binária

Requer um array ordenado. Complexidade O(log n). Implementação em Node.js:

function binarySearch(arr, target) {  let left = 0;  let right = arr.length - 1;

  while (left <= right) {    const mid = M