Какие структуры данных есть в Python?

Структуры данных в Python

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

Основные структуры

List (Список)

Упорядоченная, изменяемая коллекция элементов. Реализована как динамический массив.

my_list = [1, 2, 3, 'text', 3.14]

# Основные операции
my_list.append(4)           # O(1) amortized
my_list.insert(0, 'first')  # O(n)
my_list.pop()               # O(1)
value = my_list[0]          # O(1)

Временная сложность: доступ O(1), вставка в конец O(1), вставка в начало O(n), удаление O(n).

Tuple (Кортеж)

Упорядоченная, неизменяемая коллекция. Может использоваться как ключ в словаре.

my_tuple = (1, 2, 3)
# my_tuple[0] = 5  # TypeError — нельзя изменять

# Используется как ключ
dict_with_tuple_key = {(1, 2): 'value'}

Преимущества: безопасность (не изменяемость), использование как ключи словарей, небольшой overhead памяти.

Dictionary (Словарь)

Неупорядоченная (в Python 3.7+ упорядочена по порядку вставки) коллекция пар ключ-значение, реализованная как hash table.

my_dict = {'name': 'Alice', 'age': 30, 'city': 'Moscow'}

# Основные операции
my_dict['age']          # O(1) доступ
my_dict['salary'] = 100000  # O(1) вставка
del my_dict['city']     # O(1) удаление

# Итерация
for key, value in my_dict.items():
    print(key, value)

Ключи должны быть хешируемы (строки, числа, кортежи, но не списки или другие словари).

Set (Множество)

Неупорядоченная коллекция уникальных элементов. Реализована как hash table.

my_set = {1, 2, 3, 2, 1}  # {1, 2, 3} — дубликаты исключены

# Операции множеств
set1 = {1, 2, 3}
set2 = {2, 3, 4}

union = set1 | set2          # {1, 2, 3, 4}
intersection = set1 & set2   # {2, 3}
difference = set1 - set2     # {1}

# Проверка наличия
2 in my_set  # O(1)

Frozenset (Неизменяемое множество)

Аналогично set, но неизменяемо. Может быть ключом словаря.

my_frozenset = frozenset({1, 2, 3})
dict_key = {my_frozenset: 'value'}

Структуры из модуля collections

defaultdict

Словарь, который автоматически создаёт дефолтное значение для несуществующих ключей.

from collections import defaultdict

word_count = defaultdict(int)
for word in ['apple', 'banana', 'apple']:
    word_count[word] += 1
# {'apple': 2, 'banana': 1}

Counter

Для подсчёта частоты элементов.

from collections import Counter

my_list = ['a', 'b', 'a', 'c', 'a', 'b']
counter = Counter(my_list)
# Counter({'a': 3, 'b': 2, 'c': 1})

counter.most_common(2)  # [('a', 3), ('b', 2)]

namedtuple

Также как обычный tuple, но с именованными полями.

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p.x, p.y)  # 3 4

deque (Double-ended queue)

Оптимизирована для добавления/удаления с обоих концов. O(1) для обоих концов.

from collections import deque

q = deque([1, 2, 3])
q.append(4)      # O(1) в конец
q.appendleft(0)  # O(1) в начало
q.pop()          # O(1) удаление с конца
q.popleft()      # O(1) удаление с начала

Структуры из модуля heapq

Heap (Куча)

Минимальная куча для приоритизации элементов.

import heapq

heap = [3, 1, 4, 1, 5, 9]
heapq.heapify(heap)  # O(n)
min_val = heapq.heappop(heap)  # O(log n)
heapq.heappush(heap, 2)  # O(log n)

Структуры из модуля array

Array

Типизированный массив для хранения примитивных типов. Экономнее памяти, чем list.

import array

int_array = array.array('i', [1, 2, 3, 4, 5])

Выбор структуры на практике

В data science часто используются numpy arrays (векторизированные операции) и pandas DataFrames, которые оптимизированы для численных вычислений и работают намного быстрее, чем встроенные структуры для больших данных.