Data Structures и Algorithms: практическое применение

От теории к практике: когда использовать какие структуры данных

Многие разработчики считают алгоритмы и структуры данных оторванными от практики. Но правильный выбор структуры данных может ускорить ваш код в 100 раз и снизить потребление памяти в 10 раз. Arrays vs Linked Lists Array: const arr = [1, 2, 3, 4, 5]; Плюсы: O(1) доступ по индексу Cache-friendly (данные рядом в памяти) Простота использования Минусы: O(n) вставка/удаление в начале/середине Фиксированный размер (нужен resize) Когда использовать: случайный доступ, итерация, известный размер Linked List: class Node { constructor(value) { this.value = value; this.next = null; } } class LinkedList { constructor() { this.head = null; } insertAtHead(value) { const node = new Node(value); node.next = this.head; this.head = node; } } Плюсы: O(1) вставка/удаление в начале Динамический размер Минусы: O(n) доступ по индексу Overhead на указатели Не cache-friendly Когда использовать: частые вставки/удаления, неизвестный размер Hash Tables (Objects/Maps) // JavaScript Object const cache = {}; cache['key'] = 'value'; // Map (лучше для non-string keys) const map = new Map(); map.set(user, 'data'); map.get(user); Сложность: Вставка: O(1) Поиск: O(1) Удаление: O(1) Практическое применение: 1. Кэширование: const cache = new Map(); function expensiveOperation(n) { if (cache.has(n)) { return cache.get(n); } const result = /* вычисления */; cache.set(n, result); return result; } 2. Подсчет частоты: function countFrequency(arr) { const freq = {}; for (const item of arr) { freq[item] = (freq[item] || 0) + 1; } return freq; } 3. Группировка: function groupBy(arr, key) { return arr.reduce((acc, item) => { const group = item[key]; acc[group] = acc[group] || []; acc[group].push(item); return acc; }, {}); } Sets const uniqueItems = new Set([1, 2, 2, 3, 3, 4]); // Set {1, 2, 3, 4} Практическое применение: 1. Удаление дубликатов: const unique = [...new Set(array)]; 2. Проверка membership: const allowedUsers = new Set(['user1', 'user2', 'user3']); function checkAccess(userId) { return allowedUsers.has(userId); // O(1) } Stack (LIFO) const stack = []; // Push stack.push(1); stack.push(2); // Pop const top = stack.pop(); // 2 Практическое применение: 1. Undo/Redo: class UndoManager { constructor() { this.undoStack = []; this.redoStack = []; } do(action) { action.execute(); this.undoStack.push(action); this.redoStack = []; } undo() { if (this.undoStack.length === 0) return; const action = this.undoStack.pop(); action.undo(); this.redoStack.push(action); } redo() { if (this.redoStack.length === 0) return; const action = this.redoStack.pop(); action.execute(); this.undoStack.push(action); } } 2. Валидация скобок: function isValid(s) { const stack = []; const pairs = { '(': ')', '[': ']', '{': '}' }; for (const char of s) { if (pairs[char]) { stack.push(char); } else { const last = stack.pop(); if (pairs[last] !== char) return false; } } return stack.length === 0; } Queue (FIFO) class Queue { constructor() { this.items = []; } enqueue(item) { this.items.push(item); } dequeue() { return this.items.shift(); } } Практическое применение: 1. BFS (Breadth-First Search): function bfs(root) { const queue = [root]; const result = []; while (queue.length > 0) { const node = queue.shift(); result.push(node.value); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; } 2. Task Queue: class TaskQueue { constructor() { this.queue = []; this.processing = false; } async add(task) { this.queue.push(task); if (!this.processing) { this.process(); } } async process() { this.processing = true; while (this.queue.length > 0) { const task = this.queue.shift(); await task(); } this.processing = false; } } Priority Queue class PriorityQueue { constructor() { this.items = []; } enqueue(item, priority) { this.items.push({ item, priority }); this.items.sort((a, b) => a.priority - b.priority); } dequeue() { return this.items.shift()?.item; } } Применение: task scheduling, Dijkstra algorithm Деревья Binary Search Tree: class TreeNode { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BST { constructor() { this.root = null; } insert(value) { const node = new TreeNode(value); if (!this.root) { this.root = node; return; } let current = this.root; while (true) { if (value Применение: databases indexes, file systems Graphs Adjacency List: class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) { this.adjacencyList[vertex] = []; } } addEdge(v1, v2) { this.adjacencyList[v1].push(v2); this.adjacencyList[v2].push(v1); } dfs(start) { const result = []; const visited = {}; const traverse = (vertex) => { if (!vertex) return; visited[vertex] = true; result.push(vertex); this.adjacencyList[vertex].forEach(neighbor => { if (!visited[neighbor]) { traverse(neighbor); } }); }; traverse(start); return result; } } Применение: social networks, routing, recommendation systems Алгоритмы сортировки Quick Sort (на практике): function quickSort(arr) { if (arr.length x x === pivot); const right = arr.filter(x => x > pivot); return [...quickSort(left), ...middle, ...quickSort(right)]; } Сложность: O(n log n) average, O(n²) worst Когда какую сортировку: Почти отсортирован: Insertion Sort O(n) Много дубликатов: Quick Sort 3-way Стабильность важна: Merge Sort In-place: Heap Sort Маленький массив: Insertion Sort Поиск Binary Search: function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left Сложность: O(log n) Требование: отсортированный массив Dynamic Programming Fibonacci с мемоизацией: function fibonacci(n, memo = {}) { if (n Без DP: O(2^n) С DP: O(n) Практические советы Профилируйте! Измеряйте performance перед оптимизацией Правильная структура > clever algorithm Простота > преждевременная оптимизация Знайте Big O операций в вашем языке Заключение: Структуры данных и алгоритмы — это не абстракция, а практические инструменты. Правильный выбор структуры данных может кардинально улучшить performance. Изучайте не для интервью, а для решения реальных задач. Практикуйтесь, измеряйте, оптимизируйте только когда нужно.