Массив как структура данных: устройство в памяти и сложность операций

Что такое массив в программировании: как он лежит в памяти, почему доступ по индексу O(1), сколько стоят вставка и удаление, чем отличаются статический, динамический и двумерный массив.

11 мин чтенияструктуры данных · массивы · python

Коротко

Массив — это структура данных, в которой элементы одного размера лежат в памяти подряд, без промежутков, и каждый доступен по номеру — индексу.

ОперацияСложностьПочему
Чтение и запись по индексуO(1)O(1)адрес элемента вычисляется по формуле
Поиск значенияO(n)O(n)приходится просматривать все элементы
Вставка в начало или серединуO(n)O(n)нужно сдвинуть хвост вправо
Удаление из начала или серединыO(n)O(n)нужно сдвинуть хвост влево
Вставка и удаление в концеO(1)O(1)сдвигать нечего
  • Статический массив имеет фиксированный размер, динамический умеет расти.
  • Двумерный массив — это таблица: массив, каждый элемент которого тоже массив.
  • list в Python — динамический массив ссылок, а не «список» в смысле связного списка.

Если обозначения вроде O(n)O(n) пока непривычны, начните со статьи про Big O, а потом возвращайтесь.

Массив — что это простыми словами

Представьте камеру хранения на вокзале: длинный ряд одинаковых ячеек с номерами. Чтобы достать сумку из ячейки 37, не нужно открывать предыдущие 36 — вы просто идёте к нужному номеру.

Массив в программировании устроен так же. У него три свойства, из которых следует всё остальное:

  1. Элементы лежат подряд. Массив занимает один непрерывный кусок памяти.
  2. Элементы одного размера. Каждая ячейка занимает одинаковое число байт.
  3. У каждого элемента есть индекс. Обычно нумерация идёт с нуля.
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-битных чисел, она просит у системы один блок на 5×4=205 \times 4 = 20 байт и запоминает адрес его начала.

адрес:     1000   1004   1008   1012   1016
         ┌──────┬──────┬──────┬──────┬──────┐
значение:│  10  │  20  │  30  │  40  │  50  │
         └──────┴──────┴──────┴──────┴──────┘
индекс:     0      1      2      3      4

Раз ячейки одинаковые и стоят вплотную, адрес любого элемента считается по формуле:

адрес(i)=начало+i×размер элемента\text{адрес}(i) = \text{начало} + i \times \text{размер элемента}

Для элемента с индексом 3: 1000+3×4=10121000 + 3 \times 4 = 1012. Одно умножение и одно сложение — и мы знаем, куда смотреть.

Заодно становится понятно, почему индексация идёт с нуля. Индекс — это смещение от начала: первый элемент лежит на расстоянии ноль ячеек от старта.

Проверим формулу руками

Обычный 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] — это те же умножение, сложение и одно чтение из памяти.

Сравните со связным списком, где элементы разбросаны по памяти и каждый хранит ссылку на следующий. Чтобы добраться до сотого элемента, придётся пройти по цепочке через девяносто девять предыдущих — это O(n)O(n). Подробнее про такое устройство — в статье про список как структуру данных.

У расположения подряд есть ещё один бонус, о котором редко говорят новичкам. Процессор читает память не по одному байту, а кусками, и складывает соседние данные в быстрый кеш. Когда вы идёте по массиву циклом, следующий элемент почти всегда уже в кеше. Поэтому проход по массиву на практике заметно быстрее прохода по связному списку, хотя формально оба — O(n)O(n).

Важная оговорка: O(1)O(1) — это доступ по индексу. Поиск по значению («есть ли в массиве число 42?») в неотсортированном массиве требует просмотра всех элементов, то есть O(n)O(n). В Python это оператор in и метод index. Если массив отсортирован, поиск ускоряется до O(log⁡n)O(\log n) — бинарным поиском.

Вставка и удаление: почему 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

Сколько это стоит

Число сдвигов зависит от позиции:

Куда вставляем или откуда удаляемСдвиговСложность
Конец0O(1)O(1)
Серединаоколо n/2n/2O(n)O(n)
НачалоnnO(n)O(n)

В худшем случае двигается весь массив, поэтому в общем виде говорят: вставка и удаление — O(n)O(n).

На реальных данных разницу видно невооружённым глазом. Десять тысяч вставок в список из ста тысяч элементов:

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), цикл превращается в O(n2)O(n^2). Это одна из самых частых причин «решение верное, но не проходит по времени».

Статический и динамический массив

Статический

У статического массива размер задаётся при создании и больше не меняется. Так устроены массивы в 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 букв алфавита.

Динамический

Динамический массив снимает ограничение. Внутри это тот же статический массив, но с запасом места. Когда запас кончается, структура выделяет новый блок побольше, копирует туда элементы и освобождает старый.

Копирование стоит O(n)O(n), но случается редко, потому что блок каждый раз увеличивается с запасом. В среднем добавление в конец выходит O(1)O(1) — это называется амортизированной сложностью.

Так работают list в Python, Array в JavaScript, ArrayList в Java и std::vector в C++. Почему трюк с запасом работает и как посчитать среднюю стоимость, разобрано в отдельной статье про динамический массив — здесь повторять не будем.

СтатическийДинамический
Размерфиксированрастёт по мере надобности
Доступ по индексуO(1)O(1)O(1)O(1)
Добавление в конецO(1)O(1), пока есть местоO(1)O(1) амортизированно
Лишняя памятьнетесть запас под будущие элементы

Одномерный и двумерный массив

Всё, что было выше, — про одномерный массив: одна строка ячеек, один индекс.

Двумерный массив — это таблица со строками и столбцами, у элемента два индекса: 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. Сначала идёт вся нулевая строка, за ней первая и так далее. Адресная формула превращается в формулу индекса:

индекс(i,j)=i×число столбцов+j\text{индекс}(i, j) = i \times \text{число столбцов} + j

Это легко повторить на обычном одномерном массиве:

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] остаётся O(1)O(1).

Обход

По строкам и по столбцам:

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

Обход таблицы из nn строк и mm столбцов — O(n⋅m)O(n \cdot m). Частая ошибка — перепутать, какой индекс за что отвечает: сначала всегда строка, потом столбец. Потренироваться удобно на спиральном обходе матрицы.

Массив и список в Python

В терминах тут легко запутаться, так что по порядку.

list — это динамический массив. Называется «список», но к связному списку отношения не имеет: доступ по индексу O(1)O(1), вставка в начало O(n)O(n) — типичный массив.

Но это массив ссылок. В ячейках 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.

listarray.arrayNumPy ndarray
Что в ячейкахссылки на объектысами числасами числа
Типы элементовлюбые, вперемешкуодин числовой типодин тип
Многомерностьвложенные спискинетда
Когда братьпочти всегдамного чисел, важна памятьвычисления, матрицы

На собеседованиях и в учебных задачах под «массивом» в Python почти всегда понимают обычный list. array и NumPy нужны, когда данных много и важны память или скорость вычислений.

Когда массив подходит, а когда нет

Массив — хороший выбор, если:

  • нужно часто читать элементы по номеру;
  • данные обходятся подряд, от начала до конца;
  • добавление и удаление происходят в основном в конце.

Стоит посмотреть на другие структуры, если:

  • часто нужно вставлять и удалять в начале — берите collections.deque;
  • главная операция — «есть ли такой элемент?» — берите set или dict, там проверка в среднем O(1)O(1);
  • нужно постоянно доставать минимум или максимум — подойдёт куча (heapq).

Типичные ошибки

Выход за границы. В массиве длины n последний индекс — n - 1. Обращение к arr[n] в Python даёт IndexError, а в C молча читает чужую память.

Отрицательные индексы в Python. arr[-1] — это не ошибка, а последний элемент. Если индекс случайно ушёл в минус, программа не упадёт, а тихо вернёт неверное значение.

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

in в цикле. Проверка x in lst — это O(n)O(n). Внутри цикла по тому же списку получается O(n2)O(n^2). Для проверок на вхождение переложите данные в set.

Копия вместо ссылки. b = a не копирует массив: обе переменные указывают на один объект. Нужна копия — пишите a.copy() или a[:], а для вложенных списков — copy.deepcopy.

Срезы не бесплатны. arr[1:] создаёт новый список и копирует в него элементы — это O(n)O(n) по времени и памяти. В рекурсии передавайте индексы, а не срезы.

Массивы на собеседованиях

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

Основные приёмы, которые стоит выучить следующим шагом:

  • два указателя — два индекса идут навстречу друг другу или в одну сторону; так, например, переставляют элементы на месте без insert и pop;
  • скользящее окно — задачи про подотрезки: самый длинный, самый короткий, с заданной суммой;
  • префиксные суммы — сумма на любом отрезке за O(1)O(1) после одного прохода;
  • бинарный поиск — поиск в отсортированном массиве за O(log⁡n)O(\log n).

Разбор типовых задач с решениями собран в статье про задачи на массивы с собеседований.

Что запомнить

  • Массив — это элементы одинакового размера, лежащие в памяти подряд.
  • Адрес элемента считается по формуле начало + индекс × размер, поэтому доступ по индексу — O(1)O(1).
  • Вставка и удаление не в конце требуют сдвига хвоста — O(n)O(n).
  • Статический массив не меняет размер; динамический растёт, перевыделяя память с запасом.
  • Двумерный массив — таблица; в памяти это либо один блок построчно, либо массив ссылок на строки.
  • list в Python — динамический массив ссылок; array.array и NumPy хранят числа вплотную.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи
Алгоритмы и структуры данныхОчередь (queue): структура данных FIFO, операции и реализация на PythonОчередь как структура данных простыми словами: принцип FIFO, операции за O(1), почему list.pop(0) медленный, collections.deque, кольцевая очередь и применение в BFS и планировщиках.Алгоритмы и структуры данныхГраф как структура данных: матрица смежности, список смежности и список рёбер на PythonЧто такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.Алгоритмы и структуры данныхБинарное дерево: что это, виды, листья, полное и сбалансированное деревоБинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.