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

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

Список (list) — одна из самых важных структур данных в Python. Понимание его внутреннего устройства поможет писать более эффективный код.

1. Основные понятия

List в Python — это динамический массив переменного размера:

# Создание списка
my_list = [1, 2, 3, 4, 5]

# Список может содержать разные типы
mixed_list = [1, "hello", 3.14, True, None]

# Доступ к элементам
print(my_list[0])      # 1 (индексирование с 0)
print(my_list[-1])     # 5 (отрицательное индексирование)
print(my_list[1:4])    # [2, 3, 4] (срезирование)

2. Внутреннее устройство

Под капотом list реализован как динамический массив:

┌─────────────────────────────────────────────┐
│ List Object (PyListObject)                  │
├─────────────────────────────────────────────┤
│ size: 5                                     │  ← Количество элементов
│ allocated: 8                                │  ← Выделено память для 8
│ items: [ref1, ref2, ref3, ref4, ref5, ..] │  ← Массив ссылок
└─────────────────────────────────────────────┘
         │     │     │     │     │
         ▼     ▼     ▼     ▼     ▼
       ┌─┐   ┌─┐   ┌─┐   ┌─┐   ┌─┐
       │1│   │2│   │3│   │4│   │5│  ← Объекты Python
       └─┘   └─┘   └─┘   └─┘   └─┘

3. Создание простого списка

# Литерал
my_list = [1, 2, 3]

# Конструктор
my_list = list()         # Пустой список
my_list = list([1, 2, 3])  # Из итерируемого объекта
my_list = list(range(5))   # [0, 1, 2, 3, 4]

# List comprehension
my_list = [x for x in range(5)]       # [0, 1, 2, 3, 4]
my_list = [x * 2 for x in range(5)]   # [0, 2, 4, 6, 8]
my_list = [x for x in range(10) if x % 2 == 0]  # [0, 2, 4, 6, 8]

4. Основные операции

my_list = [1, 2, 3]

# Добавление элемента
my_list.append(4)           # [1, 2, 3, 4]

# Вставка в позицию
my_list.insert(1, 99)       # [1, 99, 2, 3, 4]

# Расширение списка
my_list.extend([5, 6, 7])   # [1, 99, 2, 3, 4, 5, 6, 7]

# Удаление элемента
my_list.remove(99)          # [1, 2, 3, 4, 5, 6, 7]

# Удаление по индексу
value = my_list.pop()       # Удаляет и возвращает последний элемент
value = my_list.pop(0)      # Удаляет и возвращает элемент на индексе 0

# Очистка списка
my_list.clear()             # []

5. Сложность операций

# O(1) — константное время
my_list[0]              # Доступ по индексу
my_list.append(item)    # Добавление в конец (амортизированное)

# O(n) — линейное время
my_list.insert(0, item) # Вставка в начало (нужно сдвинуть все элементы)
my_list.remove(item)    # Поиск и удаление
my_list.pop(0)          # Удаление первого элемента
item in my_list         # Поиск элемента

# O(n log n) — логарифмическое время
my_list.sort()          # Сортировка (используется Timsort)

6. Динамическое расширение памяти

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

# В Python это работает автоматически, но вот как это происходит:

import sys

my_list = []
print(sys.getsizeof(my_list))  # 56 bytes (пустой список)

my_list.append(1)
print(sys.getsizeof(my_list))  # 88 bytes (выделено место для 4 элементов)

for i in range(2, 10):
    my_list.append(i)
    print(f"Length: {len(my_list)}, Size: {sys.getsizeof(my_list)} bytes")

# Вывод показывает, что размер удваивается (примерно)
# Length: 2, Size: 88 bytes
# Length: 3, Size: 88 bytes
# Length: 4, Size: 88 bytes
# Length: 5, Size: 120 bytes  ← Переход
# Length: 6, Size: 120 bytes
# ...

7. Срезирование (slicing)

my_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(my_list[2:5])      # [2, 3, 4]       (от индекса 2 до 5)
print(my_list[:5])       # [0, 1, 2, 3, 4] (от начала до 5)
print(my_list[5:])       # [5, 6, 7, 8, 9] (от 5 до конца)
print(my_list[::2])      # [0, 2, 4, 6, 8] (шаг 2)
print(my_list[::-1])     # [9, 8, 7, ..., 0] (реверс)
print(my_list[1:8:2])    # [1, 3, 5, 7]   (от 1 до 8 с шагом 2)

# Срезирование создает НОВЫЙ список
slice1 = my_list[2:5]
slice1[0] = 999
print(my_list)  # [0, 1, 2, 3, 4, ...] (оригинал не изменился)

8. Итерирование

my_list = [10, 20, 30, 40]

# Обычное итерирование
for item in my_list:
    print(item)  # 10, 20, 30, 40

# С индексом
for index, item in enumerate(my_list):
    print(f"{index}: {item}")  # 0: 10, 1: 20, ...

# С помощью while и индекса
i = 0
while i < len(my_list):
    print(my_list[i])
    i += 1

# Обратное итерирование
for item in reversed(my_list):
    print(item)  # 40, 30, 20, 10

9. Копирование списков

original = [1, 2, 3]

# Неправильно — просто ссылка
copy1 = original
copy1[0] = 999
print(original)  # [999, 2, 3] ← изменился оригинал!

# Правильно — поверхностная копия
copy2 = original.copy()        # или original[:]
copy2[0] = 999
print(original)  # [1, 2, 3] ← оригинал не изменился

# Глубокая копия для вложенных списков
import copy
original = [[1, 2], [3, 4]]
copy3 = copy.deepcopy(original)
copy3[0][0] = 999
print(original)  # [[1, 2], [3, 4]] ← вложенный список не изменился

10. Методы списка

my_list = [3, 1, 4, 1, 5, 9, 2, 6]

# Поиск элемента
index = my_list.index(4)       # 2 (индекс первого вхождения)
count = my_list.count(1)       # 2 (количество элементов)

# Сортировка
my_list.sort()                 # Сортирует на месте (in-place)
# [1, 1, 2, 3, 4, 5, 6, 9]

# Сортировка с функцией
my_list.sort(reverse=True)     # По убыванию
my_list.sort(key=abs)          # По абсолютному значению

# Встроенная функция sorted() создает новый список
sorted_list = sorted([3, 1, 4, 1, 5])

# Перестановка
my_list.reverse()              # Реверс на месте
reversed_list = list(reversed(my_list))  # Создает новый

11. Списковые выражения (List comprehension)

# Простое преобразование
squares = [x**2 for x in range(5)]  # [0, 1, 4, 9, 16]

# С условием
evens = [x for x in range(10) if x % 2 == 0]  # [0, 2, 4, 6, 8]

# Вложенные
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat = [x for row in matrix for x in row]  # [1, 2, 3, 4, 5, ...]

# С трансформацией и условием
result = [x*2 for x in range(10) if x % 2 == 0]  # [0, 4, 8, 12, 16]

# Производительность выше чем цикл с append()
# ✅ faster
my_list = [x for x in range(1000000)]

# ❌ slower
my_list = []
for x in range(1000000):
    my_list.append(x)

12. Многомерные списки

# Двумерный список (матрица)
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Доступ к элементу
print(matrix[0][0])  # 1
print(matrix[1][2])  # 6

# Итерирование
for row in matrix:
    for element in row:
        print(element)

# Создание матрицы
rows, cols = 3, 3
matrix = [[0 for _ in range(cols)] for _ in range(rows)]

# ❌ Неправильно — одинаковая ссылка
matrix = [[0] * 3] * 3  # Все строки указывают на один список!
matrix[0][0] = 999
print(matrix[1][0])  # 999 ← ошибка!

13. Производительность

import timeit

# append быстрее чем insert(0)
setup = "my_list = list(range(1000))"

print("append:", timeit.timeit("my_list.append(999)", setup))
print("insert(0):", timeit.timeit("my_list.insert(0, 999)", setup))
# insert(0) намного медленнее!

# List comprehension быстрее цикла
print("Comprehension:", timeit.timeit("[x for x in range(1000)]"))
print("Loop:", timeit.timeit("result = []; [result.append(x) for x in range(1000)]"))

14. Практический пример: удаление дубликатов

my_list = [1, 2, 2, 3, 3, 3, 4, 5, 5]

# Способ 1: list(set()) — теряет порядок
unique = list(set(my_list))  # [1, 2, 3, 4, 5]

# Способ 2: сохранить порядок
seen = set()
unique = []
for item in my_list:
    if item not in seen:
        unique.append(item)
        seen.add(item)
# [1, 2, 3, 4, 5]

# Способ 3: dict (Python 3.7+)
unique = list(dict.fromkeys(my_list))  # [1, 2, 3, 4, 5]

Ключевые выводы

✅ List — динамический массив с амортизированной O(1) для append ✅ Индексирование и срезирование — мощные инструменты ✅ List comprehension — быстро и читаемо ✅ Следи за копированием — поверхностная vs глубокая копия ✅ Вставка в начало медленная — O(n) операция ✅ Поиск элемента медленный — O(n), используй set для частых поисков ✅ Понимай сложность операций — для оптимизации кода

Структура List в Python — фундамент практически всего что ты пишешь.