Алгоритмы и структуры данных на JavaScript: полное руководство для Node.js

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

Алгоритмы и структуры данных на JavaScript (Node.js): от основ до продвинутых техник

Понимание алгоритмов и структур данных — фундаментальный навык для любого разработчика, работающего с JavaScript, особенно в среде Node.js. Без этого знания невозможно создавать эффективные, масштабируемые и быстрые приложения. В этой статье мы разберем ключевые концепции, которые помогут вам писать оптимизированный код и успешно проходить технические собеседования.

Почему алгоритмы и структуры данных важны для Node.js?

Node.js, построенный на движке V8, позволяет выполнять JavaScript на сервере. Здесь, в отличие от браузера, производительность имеет критическое значение: сервер обрабатывает тысячи запросов одновременно. Неправильный выбор структуры данных может привести к замедлению работы в сотни раз. Например, поиск элемента в массиве из 10 000 записей может занять 0.1 мс, а в связанном списке — 10 мс. Разница очевидна.

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

Массивы (Array) — базовый, но мощный инструмент. Быстрый доступ по индексу (O(1)), но медленная вставка/удаление в начале (O(n)).
Хеш-таблицы (Object, Map) — идеальны для хранения пар "ключ-значение". Средняя сложность операций — O(1).
Связанные списки (LinkedList) — эффективны для частых вставок и удалений в середине списка.
Стеки и очереди (Stack, Queue) — незаменимы при обработке потоков данных (например, задачи в event loop).
Деревья (Binary Tree, BST) — для иерархических данных и быстрого поиска.
Графы (Graph) — для моделирования связей (социальные сети, маршруты).

Базовые алгоритмы сортировки и поиска в JavaScript

Рассмотрим две классические задачи: сортировка массива и бинарный поиск. В Node.js эти алгоритмы реализуются напрямую, без сторонних библиотек.

Быстрая сортировка (Quick Sort)

Это один из самых эффективных алгоритмов со средней сложностью O(n log n). Работает по принципу "разделяй и властвуй".

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// Пример использования
const numbers = [34, 7, 23, 32, 5, 62];
console.log(quickSort(numbers)); // [5, 7, 23, 32, 34, 62]

Бинарный поиск (Binary Search)

Алгоритм для отсортированных массивов. Сложность O(log n) — на порядок быстрее линейного поиска.

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // элемент не найден
}

const sortedArray = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedArray, 7)); // 3

Хеш-таблицы: когда производительность имеет значение

В Node.js хеш-таблицы реализованы через встроенные объекты Map и Object. Они обеспечивают доступ к данным за O(1) в среднем. Однако важно понимать, как избежать коллизий и потери производительности.

Пример: подсчет частоты слов с использованием Map

function countWords(text) {
  const wordMap = new Map();
  const words = text.toLowerCase().split(/\W+/);

  for (const word of words) {
    if (word) {
      wordMap.set(word, (wordMap.get(word) || 0) + 1);
    }
  }

  return wordMap;
}

const text = "JavaScript и Node.js. JavaScript — это язык программирования.";
console.log(countWords(text));
// Map(8) { 'javascript' => 2, 'и' => 1, 'node' => 1, 'js' => 1, 'это' => 1, 'язык' => 1, 'программирования' => 1 }

Важно: В Node.js используйте Map вместо Object для частых операций вставки/удаления — он оптимизирован для таких сценариев.

Графы и обход в глубину (DFS) для Node.js

Графы часто используются в задачах маршрутизации, анализа зависимостей и социальных сетей. Рассмотрим реализацию обхода в глубину (Depth-First Search) на примере графа, представленного списком смежности.

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList.get(vertex1).push(vertex2);
    this.adjacencyList.get(vertex2).push(vertex1); // для неориентированного графа
  }

  dfs(startVertex) {
    const visited = new Set();
    const result = [];

    const dfsRecursive = (vertex) => {
      if (!vertex) return;
      visited.add(vertex);
      result.push(vertex);

      const neighbors = this.adjacencyList.get(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfsRecursive(neighbor);
        }
      }
    };

    dfsRecursive(startVertex);
    return result;
  }
}

// Пример использования
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');

console.log(graph.dfs('A')); // ['A', 'B', 'D', 'C']

Этот алгоритм полезен для поиска путей, проверки связности графа и решения задач на backtracking.

Заключение

Алгоритмы и структуры данных на JavaScript (Node.js) — это не просто теория для собеседований. Это практические инструменты, которые напрямую влияют на производительность вашего кода. Начните с освоения массивов, хеш-