Головна » Розробка » JavaScript: Структури даних та алгоритми

JavaScript: Структури даних та алгоритми

JavaScript

JavaScript часто використовують для розробки фронтенд-додатків, але ця мова також поширена на бекенді завдяки Node.js. Незалежно від сфери застосування, знання структур даних і алгоритмів є важливою складовою для розробників, оскільки вони впливають на ефективність та підтримку коду. У цій статті ми розглянемо, які структури даних доступні в JavaScript, як їх застосовувати на практиці, а також обговоримо кілька базових алгоритмів, без яких не обходиться жоден серйозний проєкт.

Чому це важливо

  1. Продуктивність.
    Правильний вибір структури даних (масив, список, хеш-таблиця) може радикально змінити швидкодію додатка.
  2. Зручність коду.
    Якщо структура відповідає задачі (наприклад, Set для унікальних елементів), код стає читабельнішим і легше підтримується.
  3. Класичні алгоритми.
    Сортування, пошук, робота з графами — усе це прямо чи опосередковано знадобиться для оптимізації.

Структури даних у JavaScript

Масив (Array)

Найпоширеніша структура даних у JS. Відрізняється від традиційних масивів у мовах на кшталт C++ чи Java, адже насправді це об’єкт із числовими індексами. Проте для більшості випадків можна вважати його динамічним масивом.

const arr = [10, 20, 30];
arr.push(40); // додає елемент у кінець
arr.pop();    // видаляє останній елемент
console.log(arr[1]); // 20

Порада: масиви підходять для більшості операцій, де потрібен швидкий доступ за індексом і швидке додавання в кінець. Однак вставка чи видалення елементу всередині вимагає O(n) часу.

Об’єкт (Object)

Об’єкти в JavaScript часто використовують як хеш-таблиці (key-value). Але вони мають обмеження, адже ключі завжди перетворюються на рядки. Також є ризик конфлікту з “вбудованими” ключами в prototype.

const obj = {};
obj['name'] = 'Alice';
obj.age = 25;
console.log(obj.name, obj.age);

Починаючи з ECMAScript 2015, з’явилися Map і Set, які точніше реалізують ідею “словника” та “множини”.

Map

Map — це структура ключ-значення, схожа на об’єкт, проте ключі можуть бути будь-якого типу (навіть об’єктами чи функціями).

const map = new Map();
map.set('name', 'Alice');
map.set({ id: 1 }, 'UserOne');
console.log(map.get('name')); // 'Alice'
console.log(map.size); // 2

Основні переваги:

  • будь-який тип даних може бути ключем (не тільки рядок);
  • упорядковані ітерації (в order вставки).

Set

Set — це структура, що зберігає унікальні значення. Додаючи елемент, якщо він уже присутній, операція ігнорується.

const set = new Set([10, 20, 30]);
set.add(20); 
set.add(40);
console.log(set); // Set(4) { 10, 20, 30, 40 }
console.log(set.has(10)); // true

Зручно, коли потрібно тримати унікальні елементи (наприклад, збирання унікальних ID).

WeakMap і WeakSet

Це спеціалізовані структури, схожі на Map і Set, але ключі (в WeakMap) і значення (в WeakSet) є “слабкими” посиланнями на об’єкти. Це дає переваги в автоматичному очищенні (збирач сміття прибирає об’єкт, якщо більше немає сильних посилань). Корисно для кешування без ризику “витоку” пам’яті.

Алгоритми пошуку й сортування

Пошук

Лінійний пошук (Linear search) Перевіряємо кожен елемент у масиві, поки не знайдемо потрібний. Складність O(n). Для невеликих масивів достатньо, але якщо масив дуже великий — це повільно.

Бінарний пошук (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;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Сортування

JS має вбудований метод sort(), але важливо знати, що:

  1. За замовчуванням .sort() перетворює елементи на рядки і порівнює їх лексикографічно. Тобто [10, 2] перетворюється на [“10”, “2”], де “10” < “2” лексикографічно.
  2. Для числового сортування часто треба вказувати власну функцію порівняння.
const numbers = [10, 2, 30];
numbers.sort((a, b) => a - b); // [2, 10, 30]

При використанні .sort() всередині реалізовано алгоритм Timsort (O(n log n) у середньому). У більшості випадків цього достатньо.

Графи, дерева і колекції

Хоча вбудованих структур (Tree чи Graph) в JS немає, можна реалізувати самостійно:

  • Дерево: створити клас Node з children і методами для обходу (DFS, BFS).
  • Граф: використати Map для adjacency list (наприклад, ключ – вершина, значення – список сусідів).

Основні алгоритми:

  • BFS (пошук у ширину). Використовується, щоб знайти найкоротший шлях у невагомому графі чи мінімальну кількість кроків.
  • DFS (пошук у глибину). Зручно при обході дерево- або графоподібних структур.
  • Dijkstra. Якщо потрібно шукати найкоротші шляхи у графі з вагами.

Приклад BFS у графі:

function bfs(start, graph) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);

  while (queue.length) {
    const current = queue.shift();
    console.log(current);

    for (const neighbor of graph.get(current) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

У graph зберігається Map, де ключі — назви вершин, а значення — масив суміжних вершин.

Пам’ятайте, що в JS відсутнє вбудоване API для графів, доведеться робити все вручну.

Оптимізація із використанням структур

Як правильно підбирати структуру даних?

  • Якщо потрібен швидкий доступ за індексом і часто додають елементи в кінець — Array.
  • Якщо важлива унікальність — Set.
  • Якщо потрібні ключ:значення зі швидким пошуком — Map.
  • Якщо хочемо незмінні структури — застосовувати бібліотеки (immutable.js, наприклад) або нові пропозиції Records and Tuples (але вони ще не у фінальному стандарті).

Висновок

Структури даних (Array, Map, Set, Tree, Graph) і алгоритми (пошук, сортування, BFS/DFS) — це основа для ефективного коду. У JavaScript, незважаючи на те, що мова спочатку задумувалася як проста для браузерних задач, зараз є достатньо інструментів для реалізації як базових, так і складних структур. Важливо розуміти, як працюють масиви, об’єкти, Map та Set, щоб вибирати правильний інструмент для конкретної задачі. А вміння застосовувати алгоритми (лінійний або бінарний пошук, сортування, обходи у графах) допоможе створювати швидші й надійніші застосунки, які будуть добре масштабуватися разом із проєктом.