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

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

Каждый разработчик JavaScript рано или поздно сталкивается с необходимостью глубокого понимания алгоритмов и структур данных. Независимо от того, пишете ли вы фронтенд на React или бэкенд на Node.js, знание того, как эффективно организовывать и обрабатывать данные, является ключевым навыком. В этой статье мы разберём базовые структуры данных и популярные алгоритмы с практическими примерами на JavaScript для среды Node.js.

Зачем изучать алгоритмы и структуры данных?

Алгоритмы и структуры данных — это фундамент, на котором строится любое приложение. Правильный выбор структуры данных может ускорить выполнение программы в десятки раз. Например, поиск элемента в массиве из 10 000 элементов может занять до 10 000 операций, а в хеш-таблице — всего одну операцию. Понимание этих принципов помогает:

• Писать более производительный код
• Эффективно использовать память
• Проходить технические собеседования
• Понимать внутреннее устройство популярных библиотек и фреймворков

Основные структуры данных в JavaScript

Массивы (Arrays)

Массивы — самая распространённая структура данных в JavaScript. Они хранят элементы в последовательном порядке и предоставляют доступ по индексу за O(1). В Node.js массивы особенно полезны для работы с потоками данных.

// Пример работы с массивами в Node.js
const numbers = [5, 2, 9, 1, 5, 6];

// Добавление элемента в конец
numbers.push(10);  // [5, 2, 9, 1, 5, 6, 10]

// Удаление последнего элемента
const last = numbers.pop();  // 10

// Поиск элемента
const index = numbers.findIndex(num => num === 9);  // 2

// Фильтрация
const filtered = numbers.filter(num => num > 5);  // [9, 6]

console.log(`Результат фильтрации: ${filtered}`);

Стек (Stack)

Стек работает по принципу LIFO (Last In, First Out). Это идеальная структура для задач, где нужен доступ к последнему добавленному элементу: история действий (undo/redo), проверка скобок, обход графов.

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

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

  pop() {
    if (this.isEmpty()) return null;
    return this.items.pop();
  }

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

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

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

// Пример: проверка правильности скобок
function isValidParentheses(str) {
  const stack = new Stack();
  const pairs = { '(': ')', '{': '}', '[': ']' };

  for (let char of str) {
    if (pairs[char]) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (pairs[last] !== char) return false;
    }
  }

  return stack.isEmpty();
}

console.log(isValidParentheses("({[]})"));  // true
console.log(isValidParentheses("({[})"));   // false

Очередь (Queue)

Очередь работает по принципу FIFO (First In, First Out). Она незаменима для обработки задач в порядке их поступления: планировщики задач, очереди сообщений, BFS (обход в ширину).

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

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

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

  isEmpty() {
    return this.front === this.rear;
  }

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

// Пример: симуляция очереди печати
const printQueue = new Queue();
printQueue.enqueue("document1.pdf");
printQueue.enqueue("document2.pdf");
printQueue.enqueue("photo.jpg");

while (!printQueue.isEmpty()) {
  console.log(`Печатается: ${printQueue.dequeue()}`);
}

Связный список (Linked List)

Связный список состоит из узлов, каждый из которых содержит данные и ссылку на следующий узел. В отличие от массива, вставка и удаление в середине списка выполняются за O(1), если у вас есть ссылка на нужный узел.

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() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(' → '));
  }
}

// Пример использования
const list = new LinkedList();
list.append(10);
list.append(20);
list.prepend(5);
list.print();  // 5 → 10 → 20

Популярные алгоритмы на JavaScript

Алгоритмы сортировки

Сортировка — одна из самых частых операций. Рассмотрим два классических алгоритма: быстрая сортировка (Quick Sort) и сортировка слиянием (Merge Sort).

// Быстрая сортировка (Quick Sort)
function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

  for (let item of arr) {
    if (item < pivot) left.push(item);
    else if (item > pivot) right.push(item);
    else equal.push(item);
  }

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

// Сортировка слиянием (Merge Sort)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return [...result, ...