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

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

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

Начать курс

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

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

1. Базовые структуры данных: стек, очередь и связный список

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

Стек (LIFO)

Стек работает по принципу "последний пришел — первый ушел". Реализуем его на основе массива:

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

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

  pop() {
    return this.items.pop();
  }

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

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

// Пример использования
const stack = new Stack();
stack.push('Page 1');
stack.push('Page 2');
console.log(stack.pop()); // 'Page 2'

Очередь (FIFO)

Очередь полезна для обработки задач в порядке поступления. Реализация с использованием класса:

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

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

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

  peek() {
    return this.items[this.front];
  }

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

// Пример
const queue = new Queue();
queue.enqueue('Task 1');
queue.enqueue('Task 2');
console.log(queue.dequeue()); // 'Task 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() {
    const arr = [];
    let current = this.head;
    while (current) {
      arr.push(current.value);
      current = current.next;
    }
    return arr;
  }
}

// Пример
const list = new LinkedList();
list.append(10);
list.append(20);
list.prepend(5);
console.log(list.print()); // [5, 10, 20]

2. Алгоритмы поиска: линейный и бинарный

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

Линейный поиск

Подходит для неотсортированных данных. Сложность O(n):

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

console.log(linearSearch([3, 7, 1, 9, 4], 9)); // 3

Бинарный поиск

Требует отсортированного массива. Сложность O(log n). Реализация на Node.js:

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

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

    if (guess === target) {
      return mid;
    }
    if (guess > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}

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

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

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

Пузырьковая сортировка (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 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 unsorted = [10, 5, 2, 3, 8, 6, 1];
console.log(quickSort(unsorted)); // [1, 2, 3, 5, 6, 8, 10]