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

Разница между массивами и списками

  1. Статическая типизация
    Массивы, в отличие от списков, являются структурой данных со статической типизацией. Это значит, что в одном массиве могут храниться элементы только одного типа (например, только целые числа или только числа с плавающей точкой). В списках же могут одновременно находиться элементы разных типов: целые числа, строки, числа с плавающей точкой — что угодно. В случае пайтона в массивах могут быть числа целые и с плавающей точкой. 

  2. Динамический vs статический размер

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

    • Массивы — это статическая структура данных. При их создании нужно заранее определить, сколько в них будет элементов, и изменить этот размер в дальнейшем нельзя (без пересоздания массива).

Пример создания массива

import array  
arr = array.array('f', [0.5, 2.0, 1.5])  # 'f' — тип данных (float)  
print(arr[1])  # Выведет 2.0

Сложность операций с массивами

  • Доступ к элементу по индексу: O(1)
    Массив — это упорядоченная структура данных, где каждый элемент имеет свой индекс. Обращение к любому элементу (первому, последнему или среднему) занимает одинаковое время.

  • Поиск элемента: O(n)
    Поиск выполняется линейно (перебором), поэтому чем больше массив, тем дольше он занимает.

  • Вставка и удаление: O(n)
    При вставке или удалении элемента все последующие элементы смещаются (вправо или влево), что требует времени, пропорционального размеру массива.