JavaScript для алгоритмов: базовые структуры данных с задачами

Структуры данных — это основа алгоритмов. Если вы знаете, что такое стек, очередь и хэш-таблица, и понимаете, когда какую использовать — большинство задач на собеседованиях становится в разы проще.

Разбираем 7 ключевых структур данных на JavaScript: от массивов до деревьев. С реализацией, сложностью операций и задачами для практики.

Массив (Array)

Массив — самая базовая структура данных. В JavaScript массив — это объект с числовыми ключами и специальными методами.

Операции

*Амортизированная сложность — из-за возможного перераспределения памяти.

Встроенные методы для алгоритмов

const arr = [3, 1, 4, 1, 5, 9, 2, 6];

// Сортировка
arr.sort((a, b) => a - b); // [1, 1, 2, 3, 4, 5, 6, 9]

// Разворот
arr.reverse(); // [9, 6, 5, 4, 3, 2, 1, 1]

// Поиск
arr.indexOf(5); // 2
arr.includes(9); // true
arr.find((x) => x > 4); // 9

// Преобразование
const doubled = arr.map((x) => x * 2);
const evens = arr.filter((x) => x % 2 === 0);
const sum = arr.reduce((acc, x) => acc + x, 0);

// Срез и вставка
arr.slice(1, 4); // [6, 5, 4] — без изменения оригинала
arr.splice(2, 1, 10); // удалить 1 элемент начиная с позиции 2, вставить 10

Задача 1: Два числа с заданной суммой

Дан отсортированный массив и число target. Найдите два элемента, сумма которых равна target.

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

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }

  return [-1, -1];
}

twoSumSorted([2, 7, 11, 15], 9); // [0, 1]

Задача 2: Повернуть массив на 90 градусов

Поверните матрицу n x n по часовой стрелке.

function rotate(matrix) {
  const n = matrix.length;

  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }

  for (let row of matrix) {
    row.reverse();
  }

  return matrix;
}

rotate([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]);
// [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Стек (Stack)

Стек — структура данных «последним пришёл — первым вышел» (LIFO). Как стопка тарелок: кладёте сверху, снимаете сверху.

Операции

Реализация на массиве

const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]

stack.pop();  // 3, стек: [1, 2]
stack.pop();  // 2, стек: [1]

stack[stack.length - 1]; // 1 (peek)

Массив в JavaScript идеально подходит для стека — push и pop работают за O(1).

Задача 3: Проверка правильных скобок

Данная строка содержит ()[]{}. Проверьте, что скобки расставлены правильно.

function isValid(s) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    } else {
      if (stack.pop() !== pairs[char]) return false;
    }
  }

  return stack.length === 0;
}

isValid("()[]{}"); // true
isValid("(]");     // false
isValid("([)]");   // false
isValid("{[()]}"); // true

Задача 4: Реализовать мини-калькулятор

Вычислите значение арифметического выражения в постфиксной записи (обратная польская нотация).

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if ("+-*/".includes(token)) {
      const b = stack.pop();
      const a = stack.pop();

      switch (token) {
        case "+": stack.push(a + b); break;
        case "-": stack.push(a - b); break;
        case "*": stack.push(a * b); break;
        case "/": stack.push(Math.trunc(a / b)); break;
      }
    } else {
      stack.push(Number(token));
    }
  }

  return stack[0];
}

evalRPN(["2", "1", "+", "3", "*"]); // 9 → ((2 + 1) * 3)
evalRPN(["4", "13", "5", "/", "+"]); // 6 → (4 + (13 / 5))

Очередь (Queue)

Очередь — структура данных «первым пришёл — первым вышел» (FIFO). Как очередь в магазине: кто встал раньше, того обслужат раньше.

Операции

*Для массива — O(n), потому что нужно сдвинуть все элементы. Для связного списка — O(1).

Реализация на массиве

const queue = [];

queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]

queue.shift(); // 1, очередь: [2, 3]
queue.shift(); // 2, очередь: [3]

Задача 5: Ближайший больше элемент справа

Для каждого элемента массива найдите ближайший больший элемент справа. Если такого нет — -1.

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];

  for (let i = nums.length - 1; i >= 0; i--) {
    while (stack.length && stack[stack.length - 1] <= nums[i]) {
      stack.pop();
    }
    result[i] = stack.length ? stack[stack.length - 1] : -1;
    stack.push(nums[i]);
  }

  return result;
}

nextGreaterElement([4, 5, 2, 25]); // [5, 25, 25, -1]
nextGreaterElement([13, 7, 6, 12]); // [-1, 12, 12, -1]

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

Связный список — цепочка узлов, где каждый хранит значение и ссылку на следующий. В отличие от массива, элементы не хранятся подряд в памяти.

Зачем нужен

• Вставка/удаление в начало за O(1) (в массиве — O(n))
• Динамический размер без перераспределения памяти
• Основа для стека, очереди, графов

Реализация

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

// Создание списка: 1 → 2 → 3
const head = new ListNode(1,
  new ListNode(2,
    new ListNode(3)
  )
);

// Обход
function traverse(head) {
  let current = head;
  while (current) {
    console.log(current.val);
    current = current.next;
  }
}

// Вставка в начало
function prepend(head, val) {
  return new ListNode(val, head);
}

// Удаление узла по значению
function remove(head, val) {
  if (!head) return null;
  if (head.val === val) return head.next;
  head.next = remove(head.next, val);
  return head;
}

Операции

Задача 6: Разворот связного списка

Разворачивает односвязный список.

function reverseList(head) {
  let prev = null;
  let current = head;

  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev;
}

Задача 7: Обнаружение цикла

Проверьте, есть ли в связном списте цикл (алгоритм Флойда — «черепаха и заяц»).

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;
}

Хэш-таблица (Map / Object)

Хэш-таблица хранит пары ключ-значение. В JavaScript это Map и обычные объекты.

Операции

Map vs Object

// Object — ключи только строки/символы
const obj = {};
obj["key"] = 1;
obj[123] = 2; // ключ становится "123"

// Map — любые ключи
const map = new Map();
map.set("key", 1);
map.set(123, 2);     // ключ — число 123
map.set(true, 3);    // ключ — булево значение

map.get(123); // 2
map.size;     // 3

Задача 8: Два массива — общие элементы

Найдите пересечение двух массивов (уникальные элементы).

function intersection(nums1, nums2) {
  const set = new Set(nums1);
  const result = [];

  for (const num of nums2) {
    if (set.has(num)) {
      result.push(num);
      set.delete(num);
    }
  }

  return result;
}

intersection([1, 2, 2, 1], [2, 2]); // [2]
intersection([4, 9, 5], [9, 4, 9, 8, 4]); // [9, 4]

Задача 9: Подстрока без повторов

Найдите длину самой длинной подстроки без повторяющихся символов.

function lengthOfLongestSubstring(s) {
  const map = new Map();
  let maxLen = 0;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      left = map.get(s[right]) + 1;
    }
    map.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

lengthOfLongestSubstring("abcabcbb"); // 3
lengthOfLongestSubstring("bbbbb");    // 1

Множество (Set)

Множество хранит только уникальные значения. Аналог Set в математике.

Операции

Примеры

const set = new Set([1, 2, 3, 2, 1]);
set.size; // 3

set.add(4);
set.delete(1);
set.has(2); // true

// Быстрое удаление дубликатов из массива
const arr = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(arr)]; // [1, 2, 3]

// Множественные операции
const a = new Set([1, 2, 3]);
const b = new Set([2, 3, 4]);

// Пересечение
const intersectionSet = new Set([...a].filter((x) => b.has(x))); // {2, 3}

// Объединение
const union = new Set([...a, ...b]); // {1, 2, 3, 4}

// Разность
const diff = new Set([...a].filter((x) => !b.has(x))); // {1}

Задача 10: Палиндромная перестановка

Проверьте, можно ли составить палиндром из строки (переставив символы).

function canPermutePalindrome(s) {
  const charCount = new Map();

  for (const char of s) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }

  let oddCount = 0;
  for (const count of charCount.values()) {
    if (count % 2 !== 0) oddCount++;
    if (oddCount > 1) return false;
  }

  return true;
}

canPermutePalindrome("code"); // false
canPermutePalindrome("carerac"); // true

Деревья (Tree)

Дерево — структура данных с узлами, каждый из которых имеет значение и ссылки на дочерние узлы. Бинарное дерево — каждый узел имеет не более двух детей.

Бинарное дерево поиска (BST)

Для каждого узла: левое поддерево < узел < правое поддерево. Позволяет искать за O(log n).

Реализация

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

//      4
//     / \
//    2   6
//   / \ / \
//  1  3 5  7

const root = new TreeNode(4,
  new TreeNode(2,
    new TreeNode(1),
    new TreeNode(3)
  ),
  new TreeNode(6,
    new TreeNode(5),
    new TreeNode(7)
  )
);

Обходы дерева

// In-order (левый → корень → правый) — отсортированный порядок
function inorder(root) {
  if (!root) return [];
  return [
    ...inorder(root.left),
    root.val,
    ...inorder(root.right),
  ];
}

// Pre-order (корень → левый → правый) — для копирования дерева
function preorder(root) {
  if (!root) return [];
  return [
    root.val,
    ...preorder(root.left),
    ...preorder(root.right),
  ];
}

// Post-order (левый → правый → корень) — для удаления дерева
function postorder(root) {
  if (!root) return [];
  return [
    ...postorder(root.left),
    ...postorder(root.right),
    root.val,
  ];
}

// BFS (по уровням)
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const level = [];
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

inorder(root);     // [1, 2, 3, 4, 5, 6, 7]
preorder(root);    // [4, 2, 1, 3, 6, 5, 7]
levelOrder(root);  // [[4], [2, 6], [1, 3, 5, 7]]

Операции

Задача 11: Максимальная глубина дерева

Найдите максимальную глубину бинарного дерева.

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

maxDepth(root); // 3

Задача 12: Проверка симметричности дерева

Проверьте, является ли дерево зеркальным относительно своей оси.

function isSymmetric(root) {
  function isMirror(t1, t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (
      t1.val === t2.val &&
      isMirror(t1.left, t2.right) &&
      isMirror(t1.right, t2.left)
    );
  }

  return isMirror(root.left, root.right);
}

Шпаргалка: какую структуру выбрать

Где практиковаться

Эти структуры данных — фундамент для любых алгоритмов. Знать их теорию — хорошо. Уметь реализовать и использовать на практике — лучше.

Попробуйте решить задачи на Девстанции — там есть десятки задач, которые тренируют работу с массивами, стеками, очередями и деревьями. AI проверит ваш код и подскажет, если есть более эффективное решение.

А если готовитесь к собеседованию — посмотрите паттерны решения задач, чеклист из 50 вопросов и план подготовки за неделю.