Алгоритмы и структуры данных на JavaScript для начинающих

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

Любая программа — это не просто набор инструкций, а способ эффективного управления данными. Для начинающих разработчиков на JavaScript (особенно в среде Node.js) понимание алгоритмов и структур данных — это не просто академическая задача, а практический навык, который напрямую влияет на производительность и читаемость кода.

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

Основные структуры данных в JavaScript (Node.js)

В JavaScript встроено несколько структур данных, но для глубокого понимания нужно уметь реализовывать их вручную. Это даёт контроль над памятью и скоростью выполнения.

Массивы (Array)

Массивы в JS — это динамические списки. Они идеально подходят для хранения упорядоченных данных. Однако важно помнить, что вставка или удаление элемента в начале массива (unshift/shift) — операция O(n), так как требует сдвига всех элементов.

// Создание массива
const fruits = ['apple', 'banana', 'cherry'];

// Добавление в конец (O(1))
fruits.push('orange');

// Удаление с конца (O(1))
fruits.pop();

// Поиск элемента (O(n))
const index = fruits.indexOf('banana');
console.log(index); // 1

Стеки (Stack)

Стек работает по принципу LIFO (Last In, First Out). Это незаменимая структура для обработки вызовов функций, отмены действий (undo) или проверки скобок в коде.

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

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

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

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

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

// Пример использования: проверка скобок
const stack = new Stack();
const str = '({[]})';
let isValid = true;

for (let char of str) {
    if (char === '(' || char === '{' || char === '[') {
        stack.push(char);
    } else {
        const last = stack.pop();
        if (
            (char === ')' && last !== '(') ||
            (char === '}' && last !== '{') ||
            (char === ']' && last !== '[')
        ) {
            isValid = false;
            break;
        }
    }
}

console.log(isValid && stack.isEmpty()); // true

Очереди (Queue)

Очередь работает по принципу FIFO (First In, First Out). Она используется для управления задачами, обработки запросов в веб-серверах на Node.js или для реализации буферов.

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 taskQueue = new Queue();
taskQueue.enqueue('Задача 1');
taskQueue.enqueue('Задача 2');
console.log(taskQueue.dequeue()); // Задача 1

Алгоритмы поиска на JavaScript

Поиск данных — одна из самых частых операций. Рассмотрим два базовых алгоритма: линейный и бинарный поиск.

Линейный поиск (Linear Search)

Проходит по каждому элементу массива, пока не найдёт нужный. Сложность: O(n). Подходит для небольших или неотсортированных массивов.

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Возвращаем индекс
        }
    }
    return -1; // Не найден
}

const numbers = [10, 20, 30, 40, 50];
console.log(linearSearch(numbers, 30)); // 2
console.log(linearSearch(numbers, 100)); // -1

Бинарный поиск (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;
}

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

Алгоритмы сортировки: быстрая и пузырьковая

Сортировка — основа для многих алгоритмов. Мы рассмотрим две классические реализации.

Пузырьковая сортировка (Bubble Sort)

Простая, но медленная (O(n²)). Полезна для обучения, но не для продакшена.

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Меняем местами
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

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

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

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

    const