Algoritmos e estruturas de dados em JavaScript: guia prático

Algoritmos e estruturas de dados em JavaScript: da teoria à prática

Saber trabalhar com algoritmos e estruturas de dados é uma habilidade fundamental para qualquer desenvolvedor, independentemente da linguagem de programação. JavaScript (especialmente no ambiente Node.js) não é exceção. Neste artigo, abordaremos as estruturas de dados fundamentais e os algoritmos clássicos, implementando-os em JavaScript puro. Você verá como pilha, fila, lista encadeada, árvore e algoritmos de ordenação/busca são aplicados em problemas reais de desenvolvimento backend com Node.js.

1. Pilha e fila: estruturas básicas para gerenciamento de dados

Pilha (Stack) e fila (Queue) são estruturas de dados lineares que diferem nas regras de adição e remoção de elementos. A pilha funciona pelo princípio LIFO (Last In, First Out), enquanto a fila opera por FIFO (First In, First Out).

Implementação de pilha em JavaScript

Em JavaScript, uma pilha pode ser implementada com base em um array ou em uma lista encadeada. Vamos considerar uma versão simples com array:

class Stack {\n    constructor() {\n        this.items = [];\n    }\n\n    push(element) {\n        this.items.push(element);\n    }\n\n    pop() {\n        if (this.isEmpty()) return null;\n        return this.items.pop();\n    }\n\n    peek() {\n        if (this.isEmpty()) return null;\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Exemplo de uso\nconst stack = new Stack();\nstack.push('A');\nstack.push('B');\nstack.push('C');\nconsole.log(stack.pop());  // 'C'\nconsole.log(stack.peek()); // 'B'

A pilha é frequentemente usada para verificar o balanceamento de parênteses, implementar o botão "Voltar" no navegador ou para percorrer árvores em profundidade.

Implementação de fila em JavaScript

A fila também pode ser construída com um array, mas para melhor desempenho (evitando a reindexação ao usar shift) utilizamos uma lista encadeada ou duas pilhas. Aqui está uma implementação simples com array:

class Queue {\n    constructor() {\n        this.items = [];\n    }\n\n    enqueue(element) {\n        this.items.push(element);\n    }\n\n    dequeue() {\n        if (this.isEmpty()) return null;\n        return this.items.shift();\n    }\n\n    front() {\n        if (this.isEmpty()) return null;\n        return this.items[0];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Exemplo de uso\nconst queue = new Queue();\nqueue.enqueue(1);\nqueue.enqueue(2);\nqueue.enqueue(3);\nconsole.log(queue.dequeue()); // 1\nconsole.log(queue.front());   // 2

Filas são usadas em sistemas de gerenciamento de tarefas, em algoritmos BFS (busca em largura) e para buffer de dados em Node.js (por exemplo, streams).

2. Lista encadeada: estrutura dinâmica para inserções frequentes

Lista encadeada (Linked List) é uma sequência de nós, cada um contendo dados e uma referência ao próximo nó. Diferentemente de um array, a inserção e remoção de elementos no meio da lista são feitas em O(1) quando se tem uma referência ao nó.

Implementação de lista simplesmente encadeada

class ListNode {\n    constructor(value, next = null) {\n        this.value = value;\n        this.next = next;\n    }\n}\n\nclass LinkedList {\n    constructor() {\n        this.head = null;\n        this.tail = null;\n        this.length = 0;\n    }\n\n    append(value) {\n        const newNode = new ListNode(value);\n        if (!this.head) {\n            this.head = newNode;\n            this.tail = newNode;\n        } else {\n            this.tail.next = newNode;\n            this.tail = newNode;\n        }\n        this.length++;\n        return this;\n    }\n\n    prepend(value) {\n        const newNode = new ListNode(value, this.head);\n        this.head = newNode;\n        if (!this.tail) this.tail = newNode;\n