Массив как структура данных: устройство в памяти и сложность операций
Что такое массив в программировании: как он лежит в памяти, почему доступ по индексу O(1), сколько стоят вставка и удаление, чем отличаются статический, динамический и двумерный массив.
Коротко
Массив — это структура данных, в которой элементы одного размера лежат в памяти подряд, без промежутков, и каждый доступен по номеру — индексу.
| Операция | Сложность | Почему |
|---|---|---|
| Чтение и запись по индексу | адрес элемента вычисляется по формуле | |
| Поиск значения | приходится просматривать все элементы | |
| Вставка в начало или середину | нужно сдвинуть хвост вправо | |
| Удаление из начала или середины | нужно сдвинуть хвост влево | |
| Вставка и удаление в конце | сдвигать нечего |
- Статический массив имеет фиксированный размер, динамический умеет расти.
- Двумерный массив — это таблица: массив, каждый элемент которого тоже массив.
listв Python — динамический массив ссылок, а не «список» в смысле связного списка.
Если обозначения вроде пока непривычны, начните со статьи про Big O, а потом возвращайтесь.
Массив — что это простыми словами
Представьте камеру хранения на вокзале: длинный ряд одинаковых ячеек с номерами. Чтобы достать сумку из ячейки 37, не нужно открывать предыдущие 36 — вы просто идёте к нужному номеру.
Массив в программировании устроен так же. У него три свойства, из которых следует всё остальное:
- Элементы лежат подряд. Массив занимает один непрерывный кусок памяти.
- Элементы одного размера. Каждая ячейка занимает одинаковое число байт.
- У каждого элемента есть индекс. Обычно нумерация идёт с нуля.
nums = [5, 3, 8] print(nums[0]) # 5 — первый элемент print(nums[-1]) # 8 — последний (в Python можно считать с конца) print(len(nums)) # 3 — длина nums[1] = 10 # запись по индексу print(nums) # [5, 10, 8]
Массив — самая простая из линейных структур данных и основа для многих других: на массивах строят стеки, очереди, кучи и хеш-таблицы. Как он соотносится с остальными, смотрите в обзоре структур данных.
Как массив устроен в памяти
Оперативная память — это длинная лента пронумерованных байтов. Номер байта называется адресом. Когда программа создаёт массив из пяти 32-битных чисел, она просит у системы один блок на байт и запоминает адрес его начала.
адрес: 1000 1004 1008 1012 1016
┌──────┬──────┬──────┬──────┬──────┐
значение:│ 10 │ 20 │ 30 │ 40 │ 50 │
└──────┴──────┴──────┴──────┴──────┘
индекс: 0 1 2 3 4
Раз ячейки одинаковые и стоят вплотную, адрес любого элемента считается по формуле:
Для элемента с индексом 3: . Одно умножение и одно сложение — и мы знаем, куда смотреть.
Заодно становится понятно, почему индексация идёт с нуля. Индекс — это смещение от начала: первый элемент лежит на расстоянии ноль ячеек от старта.
Проверим формулу руками
Обычный Python прячет адреса, но модуль ctypes позволяет создать настоящий «сишный» массив и заглянуть в память напрямую:
import ctypes arr = (ctypes.c_int32 * 5)(10, 20, 30, 40, 50) base = ctypes.addressof(arr) # адрес начала массива size = ctypes.sizeof(ctypes.c_int32) # размер одного элемента: 4 байта # сами считаем адрес элемента с индексом 3 и читаем память по нему address = base + 3 * size print(ctypes.c_int32.from_address(address).value) # 40
Мы не обращались к arr[3] — мы вычислили адрес по формуле и прочитали четыре байта оттуда. Получили 40. Именно это и делает процессор, когда вы пишете arr[3].
Почему доступ по индексу — O(1)
Потому что формула не зависит от длины массива. В массиве из десяти элементов и из десяти миллионов обращение arr[i] — это те же умножение, сложение и одно чтение из памяти.
Сравните со связным списком, где элементы разбросаны по памяти и каждый хранит ссылку на следующий. Чтобы добраться до сотого элемента, придётся пройти по цепочке через девяносто девять предыдущих — это . Подробнее про такое устройство — в статье про список как структуру данных.
У расположения подряд есть ещё один бонус, о котором редко говорят новичкам. Процессор читает память не по одному байту, а кусками, и складывает соседние данные в быстрый кеш. Когда вы идёте по массиву циклом, следующий элемент почти всегда уже в кеше. Поэтому проход по массиву на практике заметно быстрее прохода по связному списку, хотя формально оба — .
Важная оговорка: — это доступ по индексу. Поиск по значению («есть ли в массиве число 42?») в неотсортированном массиве требует просмотра всех элементов, то есть . В Python это оператор in и метод index. Если массив отсортирован, поиск ускоряется до — бинарным поиском.
Вставка и удаление: почему O(n)
Плата за плотную упаковку — дыр быть не должно. Нельзя просто «втиснуть» элемент между двумя соседями: сначала нужно освободить ему место.
Вставка
Чтобы вставить 15 на позицию 1, все элементы начиная с этой позиции сдвигаются на одну ячейку вправо:
было: [10, 20, 30, 40, __]
сдвиг: [10, __, 20, 30, 40]
стало: [10, 15, 20, 30, 40]
Вот как это выглядит в коде, если делать вручную. Массив с запасом места, size — сколько ячеек реально занято:
def insert(arr, size, index, value): # идём с конца, чтобы не затереть элементы for i in range(size, index, -1): arr[i] = arr[i - 1] arr[index] = value return size + 1 data = [10, 20, 30, 40, None, None] size = 4 size = insert(data, size, 1, 15) print(data, size) # [10, 15, 20, 30, 40, None] 5
Сдвигать нужно справа налево. Если пойти слева направо, первое же присваивание затрёт соседа, и весь хвост заполнится одним значением.
Удаление
Удаление зеркально: хвост сдвигается влево и закрывает дыру.
def delete(arr, size, index): for i in range(index, size - 1): arr[i] = arr[i + 1] arr[size - 1] = None return size - 1 size = delete(data, size, 0) print(data, size) # [15, 20, 30, 40, None, None] 4
Сколько это стоит
Число сдвигов зависит от позиции:
| Куда вставляем или откуда удаляем | Сдвигов | Сложность |
|---|---|---|
| Конец | 0 | |
| Середина | около | |
| Начало |
В худшем случае двигается весь массив, поэтому в общем виде говорят: вставка и удаление — .
На реальных данных разницу видно невооружённым глазом. Десять тысяч вставок в список из ста тысяч элементов:
import timeit setup = 'lst = list(range(100_000))' print(timeit.timeit('lst.append(0)', setup=setup, number=10_000)) print(timeit.timeit('lst.insert(0, 0)', setup=setup, number=10_000))
На моём ноутбуке первая строка отрабатывает меньше чем за миллисекунду, вторая — примерно за 0,3 секунды. Точные цифры у вас будут другими, но разрыв в сотни раз сохранится.
Практический вывод: если в цикле вызывается insert(0, x), pop(0) или remove(x), цикл превращается в . Это одна из самых частых причин «решение верное, но не проходит по времени».
Статический и динамический массив
Статический
У статического массива размер задаётся при создании и больше не меняется. Так устроены массивы в C, int[] в Java, массивы фиксированной длины в Go.
Причина ограничения — та самая непрерывность. Память сразу за массивом может быть занята чем-то ещё, поэтому «дорастить» его на месте нельзя.
В Python встроенного статического массива нет, но поведение легко показать:
class StaticArray: def __init__(self, capacity): self._data = [None] * capacity self._capacity = capacity self._size = 0 def append(self, value): if self._size == self._capacity: raise OverflowError('массив заполнен') self._data[self._size] = value self._size += 1 def __getitem__(self, index): if not 0 <= index < self._size: raise IndexError('индекс вне диапазона') return self._data[index] arr = StaticArray(2) arr.append(1) arr.append(2) print(arr[1]) # 2 arr.append(3) # OverflowError: массив заполнен
Статический массив хорош, когда размер известен заранее: дни недели, клетки шахматной доски, счётчики для 26 букв алфавита.
Динамический
Динамический массив снимает ограничение. Внутри это тот же статический массив, но с запасом места. Когда запас кончается, структура выделяет новый блок побольше, копирует туда элементы и освобождает старый.
Копирование стоит , но случается редко, потому что блок каждый раз увеличивается с запасом. В среднем добавление в конец выходит — это называется амортизированной сложностью.
Так работают list в Python, Array в JavaScript, ArrayList в Java и std::vector в C++. Почему трюк с запасом работает и как посчитать среднюю стоимость, разобрано в отдельной статье про динамический массив — здесь повторять не будем.
| Статический | Динамический | |
|---|---|---|
| Размер | фиксирован | растёт по мере надобности |
| Доступ по индексу | ||
| Добавление в конец | , пока есть место | амортизированно |
| Лишняя память | нет | есть запас под будущие элементы |
Одномерный и двумерный массив
Всё, что было выше, — про одномерный массив: одна строка ячеек, один индекс.
Двумерный массив — это таблица со строками и столбцами, у элемента два индекса: matrix[i][j], где i — номер строки, j — номер столбца. Игровое поле, изображение из пикселей, таблица расстояний между городами — всё это двумерные массивы.
Создание в Python
rows, cols = 3, 4 matrix = [[0] * cols for _ in range(rows)] matrix[1][2] = 7 print(matrix) # [[0, 0, 0, 0], [0, 0, 7, 0], [0, 0, 0, 0]]
Здесь прячется самая известная ловушка для новичков. Хочется написать короче:
bad = [[0] * cols] * rows bad[1][2] = 7 print(bad) # [[0, 0, 7, 0], [0, 0, 7, 0], [0, 0, 7, 0]]
Изменили одну ячейку — поменялись три. Оператор * не копирует внутренний список, а трижды кладёт ссылку на один и тот же. Все три «строки» — один объект. Всегда создавайте строки генератором, как в первом примере.
Как таблица лежит в памяти
Память одномерна, поэтому таблицу приходится как-то в неё раскладывать. Есть два подхода.
Одним куском, строка за строкой. Так делают C и NumPy. Сначала идёт вся нулевая строка, за ней первая и так далее. Адресная формула превращается в формулу индекса:
Это легко повторить на обычном одномерном массиве:
rows, cols = 3, 4 flat = [0] * (rows * cols) def get(i, j): return flat[i * cols + j] def set_value(i, j, value): flat[i * cols + j] = value set_value(1, 2, 7) print(get(1, 2)) # 7 print(flat.index(7)) # 6, потому что 1 * 4 + 2 = 6
Массив массивов. Так устроены вложенные списки в Python и int[][] в Java. Внешний массив хранит ссылки на строки, а строки лежат в памяти где угодно. Отсюда следствие: строки могут быть разной длины («зубчатый» массив).
В обоих случаях доступ к matrix[i][j] остаётся .
Обход
По строкам и по столбцам:
grid = [[1, 2, 3], [4, 5, 6]] # по строкам for row in grid: for value in row: print(value, end=' ') # 1 2 3 4 5 6 # по столбцам for j in range(len(grid[0])): for i in range(len(grid)): print(grid[i][j], end=' ') # 1 4 2 5 3 6
Обход таблицы из строк и столбцов — . Частая ошибка — перепутать, какой индекс за что отвечает: сначала всегда строка, потом столбец. Потренироваться удобно на спиральном обходе матрицы.
Массив и список в Python
В терминах тут легко запутаться, так что по порядку.
list — это динамический массив. Называется «список», но к связному списку отношения не имеет: доступ по индексу , вставка в начало — типичный массив.
Но это массив ссылок. В ячейках list лежат не сами значения, а адреса объектов. Ссылки одного размера, поэтому формула адреса работает, а сами объекты могут быть любыми:
mixed = [1, 'два', 3.0, [4]] # так можно
Цена — память и лишний переход по ссылке при каждом чтении.
array.array — «настоящий» массив чисел. Модуль array из стандартной библиотеки хранит значения вплотную, как в C. Тип элементов задаётся при создании:
from array import array numbers = array('i', [1, 2, 3]) # 'i' — знаковое целое numbers.append(4) print(numbers[2]) # 3 print(numbers.itemsize) # 4 — байт на элемент numbers.append('пять') # TypeError
Разницу в памяти можно измерить:
import sys from array import array n = 1000 lst = list(range(n)) arr = array('i', range(n)) print(sys.getsizeof(lst)) # 8056 — только ссылки print(sys.getsizeof(arr)) # 4184 — сами числа print(sys.getsizeof(lst) + sum(sys.getsizeof(x) for x in lst)) # 36052
Цифры получены на 64-битном CPython 3.9, в других версиях они могут немного отличаться. Суть не меняется: список из тысячи чисел вместе с объектами-числами занимает в разы больше памяти, чем array.
list | array.array | NumPy ndarray | |
|---|---|---|---|
| Что в ячейках | ссылки на объекты | сами числа | сами числа |
| Типы элементов | любые, вперемешку | один числовой тип | один тип |
| Многомерность | вложенные списки | нет | да |
| Когда брать | почти всегда | много чисел, важна память | вычисления, матрицы |
На собеседованиях и в учебных задачах под «массивом» в Python почти всегда понимают обычный list. array и NumPy нужны, когда данных много и важны память или скорость вычислений.
Когда массив подходит, а когда нет
Массив — хороший выбор, если:
- нужно часто читать элементы по номеру;
- данные обходятся подряд, от начала до конца;
- добавление и удаление происходят в основном в конце.
Стоит посмотреть на другие структуры, если:
- часто нужно вставлять и удалять в начале — берите
collections.deque; - главная операция — «есть ли такой элемент?» — берите
setилиdict, там проверка в среднем ; - нужно постоянно доставать минимум или максимум — подойдёт куча (
heapq).
Типичные ошибки
Выход за границы. В массиве длины n последний индекс — n - 1. Обращение к arr[n] в Python даёт IndexError, а в C молча читает чужую память.
Отрицательные индексы в Python. arr[-1] — это не ошибка, а последний элемент. Если индекс случайно ушёл в минус, программа не упадёт, а тихо вернёт неверное значение.
Удаление во время обхода. Удаляете элемент — хвост сдвигается, и цикл перепрыгивает через следующий. Собирайте новый список или идите с конца.
in в цикле. Проверка x in lst — это . Внутри цикла по тому же списку получается . Для проверок на вхождение переложите данные в set.
Копия вместо ссылки. b = a не копирует массив: обе переменные указывают на один объект. Нужна копия — пишите a.copy() или a[:], а для вложенных списков — copy.deepcopy.
Срезы не бесплатны. arr[1:] создаёт новый список и копирует в него элементы — это по времени и памяти. В рекурсии передавайте индексы, а не срезы.
Массивы на собеседованиях
С задач на массивы начинается почти любое алгоритмическое интервью. При этом самих по себе знаний об устройстве обычно не спрашивают — проверяют, умеете ли вы ими пользоваться: не делать лишних сдвигов, не заводить лишнюю память, оценивать сложность.
Основные приёмы, которые стоит выучить следующим шагом:
- два указателя — два индекса идут навстречу друг другу или в одну сторону; так, например, переставляют элементы на месте без
insertиpop; - скользящее окно — задачи про подотрезки: самый длинный, самый короткий, с заданной суммой;
- префиксные суммы — сумма на любом отрезке за после одного прохода;
- бинарный поиск — поиск в отсортированном массиве за .
Разбор типовых задач с решениями собран в статье про задачи на массивы с собеседований.
Что запомнить
- Массив — это элементы одинакового размера, лежащие в памяти подряд.
- Адрес элемента считается по формуле
начало + индекс × размер, поэтому доступ по индексу — . - Вставка и удаление не в конце требуют сдвига хвоста — .
- Статический массив не меняет размер; динамический растёт, перевыделяя память с запасом.
- Двумерный массив — таблица; в памяти это либо один блок построчно, либо массив ссылок на строки.
listв Python — динамический массив ссылок;array.arrayи NumPy хранят числа вплотную.