Data Structures JavaScript CheatSheet 🚀

Índice

Arrays
Linked Lists
Doubly Linked Lists
Queues
Hash Tables / Maps
Trees (Binary Search Tree)

Arrays

Implementação Básica

class DynamicArray {
    constructor() {
        this.data = [];
        this.length = 0;
    }

    // O(1) - acesso por índice
    get(index) {
        return this.data[index];
    }

    // O(1) - inserção no final
    push(item) {
        this.data[this.length] = item;
        this.length++;
        return this.length;
    }

    // O(1) - remoção do final
    pop() {
        if (this.length === 0) return undefined;
        const lastItem = this.data[this.length - 1];
        delete this.data[this.length - 1];
        this.length--;
        return lastItem;
    }

    // O(n) - inserção em posição específica
    insert(index, item) {
        for (let i = this.length; i > index; i--) {
            this.data[i] = this.data[i - 1];
        }
        this.data[index] = item;
        this.length++;
    }

    // O(n) - remoção em posição específica
    delete(index) {
        for (let i = index; i < this.length - 1; i++) {
            this.data[i] = this.data[i + 1];
        }
        delete this.data[this.length - 1];
        this.length--;
    }
}

Operações Essenciais para LeetCode

// Two Pointers
function twoPointers(arr) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) {
        // lógica aqui
        left++;
        right--;
    }
}

// Sliding Window
function slidingWindow(arr, k) {
    let windowSum = 0;
    
    // Primeira janela
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    let maxSum = windowSum;
    
    // Deslizar a janela
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

Linked Lists

Implementação Otimizada

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

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

    // O(1) - inserção no início
    prepend(val) {
        const newNode = new ListNode(val);
        if (!this.head) {
            this.head = this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.size++;
    }

    // O(1) - inserção no final (com tail pointer)
    append(val) {
        const newNode = new ListNode(val);
        if (!this.head) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size++;
    }

    // O(n) - busca
    find(val) {
        let current = this.head;
        while (current) {
            if (current.val === val) return current;
            current = current.next;
        }
        return null;
    }

    // O(n) - remoção
    remove(val) {
        if (!this.head) return false;

        if (this.head.val === val) {
            this.head = this.head.next;
            if (!this.head) this.tail = null;
            this.size--;
            return true;
        }

        let current = this.head;
        while (current.next && current.next.val !== val) {
            current = current.next;
        }

        if (current.next) {
            if (current.next === this.tail) {
                this.tail = current;
            }
            current.next = current.next.next;
            this.size--;
            return true;
        }
        return false;
    }

    // Utilitários para LeetCode
    toArray() {
        const result = [];
        let current = this.head;
        while (current) {
            result.push(current.val);
            current = current.next;
        }
        return result;
    }

    static fromArray(arr) {
        const list = new LinkedList();
        for (const val of arr) {
            list.append(val);
        }
        return list;
    }
}

Patterns Essenciais para LeetCode

// Fast & Slow Pointers (Floyd's Algorithm)
function hasCycle(head) {
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

// Reverter Linked List
function reverseList(head) {
    let prev = null;
    let current = head;
    
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

// Merge Two Sorted Lists
function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    current.next = l1 || l2;
    return dummy.next;
}

Doubly Linked Lists

Implementação Completa

class DoublyListNode {
    constructor(val = 0, next = null, prev = null) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // O(1) - inserção no início
    prepend(val) {
        const newNode = new DoublyListNode(val);
        
        if (!this.head) {
            this.head = this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
        this.size++;
    }

    // O(1) - inserção no final
    append(val) {
        const newNode = new DoublyListNode(val);
        
        if (!this.tail) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.size++;
    }

    // O(1) - remoção de nó específico (quando você tem referência)
    removeNode(node) {
        if (!node) return false;

        if (node.prev) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }

        if (node.next) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }

        this.size--;
        return true;
    }

    // O(n) - busca bidirecional otimizada
    find(val) {
        // Decidir se buscar do início ou do fim
        let current;
        if (this.size <= 1) {
            current = this.head;
            while (current) {
                if (current.val === val) return current;
                current = current.next;
            }
        } else {
            // Buscar da extremidade mais próxima
            const mid = Math.floor(this.size / 2);
            let index = 0;
            current = this.head;
            
            while (current && index < mid) {
                if (current.val === val) return current;
                current = current.next;
                index++;
            }
            
            // Buscar do final
            current = this.tail;
            index = this.size - 1;
            while (current && index >= mid) {
                if (current.val === val) return current;
                current = current.prev;
                index--;
            }
        }
        return null;
    }
}

Queues

Queue usando Array (Simple mas menos eficiente)

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

    // O(1)
    enqueue(item) {
        this.items.push(item);
    }

    // O(n) - shift é custoso
    dequeue() {
        return this.items.shift();
    }

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

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

    size() {
        return this.items.length;
    }
}

Queue usando Linked List (Otimizada - RECOMENDADA)

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

    // O(1) - adicionar no final
    enqueue(val) {
        const newNode = new ListNode(val);
        
        if (!this.rear) {
            this.front = this.rear = newNode;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
        }
        this.length++;
    }

    // O(1) - remover do início
    dequeue() {
        if (!this.front) return null;
        
        const val = this.front.val;
        this.front = this.front.next;
        
        if (!this.front) {
            this.rear = null;
        }
        
        this.length--;
        return val;
    }

    peek() {
        return this.front ? this.front.val : null;
    }

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

    size() {
        return this.length;
    }
}

Priority Queue (Para LeetCode)

class PriorityQueue {
    constructor(compareFn = (a, b) => a - b) {
        this.heap = [];
        this.compare = compareFn;
    }

    enqueue(val) {
        this.heap.push(val);
        this.heapifyUp();
    }

    dequeue() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return root;
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.compare(this.heap[index], this.heap[parentIndex]) >= 0) break;
            
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    heapifyDown() {
        let index = 0;
        while (2 * index + 1 < this.heap.length) {
            const leftChild = 2 * index + 1;
            const rightChild = 2 * index + 2;
            let smallest = leftChild;

            if (rightChild < this.heap.length && 
                this.compare(this.heap[rightChild], this.heap[leftChild]) < 0) {
                smallest = rightChild;
            }

            if (this.compare(this.heap[index], this.heap[smallest]) <= 0) break;

            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }

    peek() {
        return this.heap[0] || null;
    }

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

Hash Tables / Maps

Hash Table Básica (Para entender o conceito)

class HashTable {
    constructor(size = 53) {
        this.keyMap = new Array(size);
    }

    _hash(key) {
        let total = 0;
        let WEIRD_PRIME = 31;
        for (let i = 0; i < Math.min(key.length, 100); i++) {
            let char = key[i];
            let value = char.charCodeAt(0) - 96;
            total = (total * WEIRD_PRIME + value) % this.keyMap.length;
        }
        return total;
    }

    set(key, value) {
        let index = this._hash(key);
        if (!this.keyMap[index]) {
            this.keyMap[index] = [];
        }
        
        // Verificar se a chave já existe
        for (let i = 0; i < this.keyMap[index].length; i++) {
            if (this.keyMap[index][i][0] === key) {
                this.keyMap[index][i][1] = value;
                return;
            }
        }
        
        this.keyMap[index].push([key, value]);
    }

    get(key) {
        let index = this._hash(key);
        if (this.keyMap[index]) {
            for (let i = 0; i < this.keyMap[index].length; i++) {
                if (this.keyMap[index][i][0] === key) {
                    return this.keyMap[index][i][1];
                }
            }
        }
        return undefined;
    }

    has(key) {
        return this.get(key) !== undefined;
    }

    delete(key) {
        let index = this._hash(key);
        if (this.keyMap[index]) {
            for (let i = 0; i < this.keyMap[index].length; i++) {
                if (this.keyMap[index][i][0] === key) {
                    this.keyMap[index].splice(i, 1);
                    return true;
                }
            }
        }
        return false;
    }
}

Map/Set Nativo (RECOMENDADO para LeetCode)

// Map - para quando você precisa de chave-valor
const map = new Map();
map.set('key', 'value');
map.get('key'); // 'value'
map.has('key'); // true
map.delete('key');
map.size; // tamanho
map.clear(); // limpar tudo

// Iterar Map
for (const [key, value] of map) {
    console.log(key, value);
}

// Set - para valores únicos
const set = new Set();
set.add('value');
set.has('value'); // true
set.delete('value');
set.size; // tamanho

// Converter array para set (remover duplicatas)
const uniqueArray = [...new Set(array)];

// Patterns comuns para LeetCode
function twoSum(nums, target) {
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    
    return [];
}

// Frequency Counter Pattern
function frequencyCounter(arr) {
    const freq = new Map();
    
    for (const item of arr) {
        freq.set(item, (freq.get(item) || 0) + 1);
    }
    
    return freq;
}

Trees (Binary Search Tree)

Implementação BST Completa

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    // O(log n) average, O(n) worst case
    insert(val) {
        const newNode = new TreeNode(val);
        
        if (!this.root) {
            this.root = newNode;
            return this;
        }

        let current = this.root;
        while (true) {
            if (val === current.val) return undefined; // não permitir duplicatas
            
            if (val < current.val) {
                if (!current.left) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    // O(log n) average, O(n) worst case
    search(val) {
        let current = this.root;
        
        while (current) {
            if (val === current.val) return current;
            if (val < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        
        return null;
    }

    // Encontrar valor mínimo (mais à esquerda)
    findMin(node = this.root) {
        if (!node) return null;
        while (node.left) {
            node = node.left;
        }
        return node;
    }

    // Encontrar valor máximo (mais à direita)
    findMax(node = this.root) {
        if (!node) return null;
        while (node.right) {
            node = node.right;
        }
        return node;
    }

    // Remoção (mais complexa)
    remove(val) {
        this.root = this._removeNode(this.root, val);
    }

    _removeNode(node, val) {
        if (!node) return null;

        if (val < node.val) {
            node.left = this._removeNode(node.left, val);
        } else if (val > node.val) {
            node.right = this._removeNode(node.right, val);
        } else {
            // Nó encontrado - 3 casos:
            
            // Caso 1: Nó folha (sem filhos)
            if (!node.left && !node.right) {
                return null;
            }
            
            // Caso 2: Nó com um filho
            if (!node.left) return node.right;
            if (!node.right) return node.left;
            
            // Caso 3: Nó com dois filhos
            // Encontrar o sucessor (menor valor na subárvore direita)
            const successor = this.findMin(node.right);
            node.val = successor.val;
            node.right = this._removeNode(node.right, successor.val);
        }
        
        return node;
    }
}

Algoritmos de Travessia (FUNDAMENTAIS para LeetCode)

1. In-Order Traversal (Esquerda → Raiz → Direita)

Resultado: Elementos em ordem crescente em uma BST

function inorderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        traverse(node.left);    // Esquerda
        result.push(node.val);  // Raiz
        traverse(node.right);   // Direita
    }
    
    traverse(root);
    return result;
}

// Versão iterativa (usando stack)
function inorderTraversalIterative(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current || stack.length > 0) {
        // Ir para o nó mais à esquerda
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        // Processar nó atual
        current = stack.pop();
        result.push(current.val);
        
        // Ir para subárvore direita
        current = current.right;
    }
    
    return result;
}

2. Pre-Order Traversal (Raiz → Esquerda → Direita)

Uso: Criar cópia da árvore, expressões prefix

function preorderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        result.push(node.val);  // Raiz
        traverse(node.left);    // Esquerda
        traverse(node.right);   // Direita
    }
    
    traverse(root);
    return result;
}

3. Post-Order Traversal (Esquerda → Direita → Raiz)

Uso: Deletar nós, calcular tamanho da árvore

function postorderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        traverse(node.left);    // Esquerda
        traverse(node.right);   // Direita
        result.push(node.val);  // Raiz
    }
    
    traverse(root);
    return result;
}

4. Level-Order Traversal (BFS - Breadth-First Search)

Uso: Problemas por níveis, encontrar altura

function levelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}

Algoritmos Essenciais para LeetCode

Validar se é BST

function isValidBST(root) {
    function validate(node, min, max) {
        if (!node) return true;
        
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        return validate(node.left, min, node.val) && 
               validate(node.right, node.val, max);
    }
    
    return validate(root, -Infinity, Infinity);
}

Altura da Árvore

function maxDepth(root) {
    if (!root) return 0;
    
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Árvore Balanceada

function isBalanced(root) {
    function getHeight(node) {
        if (!node) return 0;
        
        const leftHeight = getHeight(node.left);
        const rightHeight = getHeight(node.right);
        
        // Se alguma subárvore não é balanceada
        if (leftHeight === -1 || rightHeight === -1) return -1;
        
        // Se diferença de altura > 1
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        
        return 1 + Math.max(leftHeight, rightHeight);
    }
    
    return getHeight(root) !== -1;
}

Complexidades de Tempo e Espaço - Resumo

Estrutura	Acesso	Busca	Inserção	Remoção	Espaço
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)	O(n)	O(n)
Doubly LL	O(n)	O(n)	O(1)	O(1)*	O(n)
Queue	-	-	O(1)	O(1)	O(n)
Hash Table	-	O(1)**	O(1)**	O(1)**	O(n)
BST	O(log n)**	O(log n)**	O(log n)**	O(log n)**	O(n)

* quando você tem referência ao nó
** caso médio, pior caso pode ser O(n)

Dicas para LeetCode

Use Map/Set nativos do JavaScript para problemas de hash
Linked Lists: sempre considere usar dummy node para simplificar
Trees: pratique todos os tipos de travessia
Arrays: domine two pointers e sliding window
Queues: use para BFS em trees/graphs

Boa sorte nos seus estudos! 🚀

J-Pster/DataStructure-Cheatsheet-JS.md