Массив

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

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

Чтобы получить доступ к элементу Red в списке, нужно начать с его начала. В массиве же можно сразу указать индекс нужного элемента, например, a[2], и обратиться к нему напрямую.

Массивы позволяют добавлять и удалять данные в любом месте. Однако эти операции требуют больше ресурсов. Рассмотрим, как добавить элемент Green. Сначала выделяется свободное место в конце массива.

Затем мы сдвигаем данные по одному, чтобы освободить ячейку памяти в нужном месте. Сначала сместится блок Red.

Затем сместится блок Yellow. Затем на свободное место помещается блок Green.

Чтобы удалить блок Green из массива, операции выполняются в обратном порядке.

Обсудим, как массивы влияют на скорость вычислений.

Предположим, что в массиве n элементов. Благодаря тому, что к любому элементу можно получить доступ мгновенно по индексу, время его извлечения — константа, то есть O(1). Однако при добавлении нового элемента все последующие нужно сдвинуть на одну позицию. Это тоже занимает O(1) времени.

Но если попытаться добавить данные в начало массива или удалить элемент из него, потребуется O(n) операций.

В Python нет отдельного встроенного типа "массив", как в C или Java, но обычный list ведёт себя как динамический массив. Для "чистого массива" можно использовать модуль array, но чаще используют list.

import array

# Создаем массив целых чисел
numbers = array.array("i", [10, 20, 30, 40])
print(numbers)

Доступ по индексу (O(1))

print(numbers[0])  # первый элемент
print(numbers[2])  # третий элемент

Добавление элемента в конец

numbers.append(50)  # добавляем в конец
print(numbers)

Вставка элемента в середину (O(n))

numbers.insert(2, 25)  # вставим число 25 в позицию 2
print(numbers)

Главное отличие array от list:

• list может хранить разные типы данных (строки, числа, списки внутри).
• array хранит только один тип данных (например, только int). Это экономит память и ближе к "классическим" массивам в других языках.