re:re:actable
Урок 012 минуты чтения

Как использовать Array в алгоритмах?

На этой странице
Кратко

Array - главная структура данных в JavaScript-задачах. Его используют как динамический массив, стек, иногда очередь, список значений, таблицу DP и основу для сортировки, поиска и паттернов two pointers/sliding window.

Вопрос

Как использовать Array в алгоритмах и какова сложность основных операций?

Что важно знать про Array в JavaScript?

Массивы в JavaScript:

  • изменяемые;
  • имеют динамическую длину;
  • могут хранить разные типы;
  • индексируются с 0;
  • имеют методы push, pop, shift, unshift, slice, splice, map, filter, reduce, sort.
const nums = [10, 20, 30]
nums.push(40)
nums[0] = 5

Частые операции

ОперацияОбычно
arr[i]O(1)
pushamortized O(1)
popO(1)
shiftO(n)
unshiftO(n)
includesO(n)
sliceO(k)
sortзависит от реализации, обычно думай как O(n log n)

Стек на Array

const stack: number[] = []
 
stack.push(1)
stack.push(2)
 
const top = stack.pop()

push/pop хорошо подходят для stack.

Очередь на Array

const queue: number[] = []
 
queue.push(1)
queue.push(2)
const first = queue.shift()

shift() может быть дорогим, потому что элементы сдвигаются. Для больших очередей лучше хранить индекс головы.

const queue: number[] = []
let head = 0
 
queue.push(1)
queue.push(2)
 
const first = queue[head++]

Что отвечать на собеседовании?

Array в JavaScript - динамический индексируемый список. Он удобен для большинства задач, но важно знать стоимость операций: push/pop обычно быстрые, а shift/unshift могут быть O(n). Для поиска по значению includes линейный, поэтому для частых проверок принадлежности лучше использовать Set.

Что важно помнить: частые ошибки

  • Использовать shift() в BFS на большом графе.
  • Забывать, что sort() мутирует массив.
  • Использовать includes внутри цикла и получать O(n^2).
  • Создавать много копий через spread без учета памяти.
  • Путать sparse arrays и обычные плотные массивы.

Мини-шпаргалка

  • arr[i] - доступ по индексу.
  • push/pop - стек.
  • shift/unshift - осторожно, часто O(n).
  • includes - линейный поиск.
  • slice/spread создают копии.
  • sort мутирует массив.

Документация

MDN: Array.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам