Как использовать 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) |
push | amortized O(1) |
pop | O(1) |
shift | O(n) |
unshift | O(n) |
includes | O(n) |
slice | O(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мутирует массив.