Массивы и списки: основа структур данных

🎯 Зачем это нужно?

Представь, что ты создаёшь Instagram 📱. Как хранить все фотографии пользователя? Или YouTube - как управлять плейлистом из тысяч видео? А Netflix - как быстро найти фильм среди миллионов? Все эти задачи решают массивы и списки - самые базовые, но критически важные структуры данных!

💼 В реальной разработке:

• Google использует массивы для хранения результатов поиска
• Spotify хранит треки в плейлистах как списки
• Игры вроде Fortnite используют массивы для координат игроков

📚 История вопроса

Концепция массива появилась ещё в 1940-х с первыми компьютерами! Джон фон Нейман понял: чтобы программа была эффективной, данные нужно организовывать в памяти структурированно. Интересный факт: в языке FORTRAN (1957) массивы были ЕДИНСТВЕННОЙ структурой данных! 🤯

💡 Интуиция

Массив - это как шкафчики в школьной раздевалке 🏫. Каждый шкафчик имеет номер (индекс), и в каждом лежит одна вещь. Хочешь взять куртку из 15-го шкафчика? Идёшь прямо к нему - это O(1) операция!

Список - больше похож на поезд 🚂. Вагоны соединены цепочкой, чтобы добраться до 10-го вагона, нужно пройти через первые 9. Зато можно легко добавить новый вагон в любое место!

[МЕДИА: image_01] Описание: Сравнение массива (шкафчики с номерами) и связанного списка (вагоны поезда) Промпт: “educational illustration comparing array as numbered lockers vs linked list as train cars, modern flat design, tech colors blue and orange, clear indexing numbers, arrows showing connections”

📐 Формальное определение

Массив - структура данных, хранящая элементы одного типа в непрерывном блоке памяти. Доступ к элементу по индексу i: A[i] = base_address + i × element_size

Связанный список - структура данных из узлов, где каждый узел содержит данные и указатель на следующий элемент.

# Массив в Python (список с фиксированным размером)
import array
arr = array.array('i', [1, 2, 3, 4, 5])  # O(1) доступ
print(arr[2])  # Мгновенно получаем 3

# Связанный список (упрощённая реализация)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):  # O(n)
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

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

*при наличии места, иначе O(n) **при известном узле

[МЕДИА: image_02] Описание: Таблица сложности операций с визуализацией Big O Промпт: “complexity comparison table for arrays vs linked lists, Big O notation, colorful performance indicators, green for O(1), yellow for O(n), modern data visualization style”

🔍 Примеры с разбором

Пример 1: Поиск максимального элемента

def find_max(arr):
    """Находит максимальный элемент в массиве"""
    if not arr:
        return None
    
    max_val = arr[0]  # Предполагаем, что первый максимальный
    for i in range(1, len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

# Тестируем
scores = [85, 92, 78, 96, 88]  # Оценки студентов
print(find_max(scores))  # 96

Сложность: O(n) - нужно просмотреть каждый элемент Память: O(1) - используем только одну переменную max_val

Пример 2: Реверс связанного списка

def reverse_linked_list(head):
    """Разворачивает связанный список"""
    prev = None
    current = head
    
    while current:
        next_temp = current.next  # Сохраняем следующий
        current.next = prev       # Разворачиваем связь
        prev = current           # Двигаем prev
        current = next_temp      # Двигаем current
    
    return prev  # prev теперь новая голова

Визуализация:

До:  1 → 2 → 3 → 4 → None
После: None ← 1 ← 2 ← 3 ← 4

[МЕДИА: animation_01] Описание: Анимация реверса связанного списка по шагам Промпт: “step-by-step animation of linked list reversal, nodes with arrows changing direction, highlighting prev and current pointers, educational programming visualization”

Пример 3: Двумерный массив (матрица)

# Создание матрицы 3x3 для крестиков-ноликов
board = [[' ' for _ in range(3)] for _ in range(3)]

def make_move(board, row, col, player):
    """Делает ход в крестики-нолики"""
    if board[row][col] == ' ':
        board[row][col] = player
        return True
    return False

def print_board(board):
    """Выводит доску на экран"""
    for row in board:
        print(' | '.join(row))
        print('-+-+-')

# Тестируем
make_move(board, 1, 1, 'X')  # X в центр
print_board(board)

🎮 Практика

Базовый уровень 🟢

Задание 1: Напиши функцию, которая находит все чётные числа в массиве

def find_even(arr):
    # Твой код здесь
    pass

# Тест: find_even([1, 2, 3, 4, 5, 6]) должно вернуть [2, 4, 6]

Задание 2: Реализуй функцию сдвига массива влево на k позиций

def rotate_left(arr, k):
    # [1,2,3,4,5] при k=2 → [3,4,5,1,2]
    pass

Задание 3: Найди второй максимальный элемент в массиве

def second_max(arr):
    # Не используй сортировку!
    pass

Задание 4: Проверь, является ли массив палиндромом

def is_palindrome(arr):
    # [1,2,3,2,1] → True
    # [1,2,3,4] → False
    pass

Продвинутый уровень 🟡

Задание 5: Merge Sort для массивов - реализуй алгоритм слияния

def merge_sort(arr):
    """Сортировка слиянием O(n log n)"""
    # Разделяй и властвуй!
    pass

Задание 6: Реализуй стек используя связанный список

class Stack:
    def __init__(self):
        self.top = None
    
    def push(self, data):
        pass
    
    def pop(self):
        pass
    
    def peek(self):
        pass

Задание 7: Найди пересечение двух отсортированных массивов

def intersection(arr1, arr2):
    # [1,2,2,3] и [2,2,3,4] → [2,2,3]
    # Используй два указателя!
    pass

Задание 8: Циклический связанный список - детектор цикла

def has_cycle(head):
    """Алгоритм Floyd's Cycle Detection (черепаха и заяц)"""
    pass

Челлендж 🔴

Задание 9: Максимальная сумма подмассива (Kadane’s Algorithm)

def max_subarray_sum(arr):
    """
    Найди подмассив с максимальной суммой
    [-2,1,-3,4,-1,2,1,-5,4] → подмассив [4,-1,2,1] сумма = 6
    """
    pass

Задание 10: LRU Cache используя связанный список + хэш-таблица

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        # Твоя реализация
    
    def get(self, key):
        pass
    
    def put(self, key, value):
        pass

⚠️ Частые ошибки

❌ Ошибка: Выход за границы массива (IndexError)

arr = [1, 2, 3]
print(arr[5])  # Ошибка!

✅ Правильно: Всегда проверяй границы

if 0 <= index < len(arr):
    print(arr[index])

💡 Почему: Python не предотвращает выход за границы, нужно следить самому

❌ Ошибка: Путаница в указателях при работе со списками

# Потеря ссылки на голову
head = head.next  # Потеряли первый элемент!

✅ Правильно: Сохраняй ссылки перед изменением

temp = head.next
# работаем с temp
head = temp

💡 Почему: В связанных списках легко потерять узлы без сборки мусора

❌ Ошибка: Изменение списка во время итерации

arr = [1, 2, 3, 4, 5]
for item in arr:
    arr.remove(item)  # Может пропустить элементы!

✅ Правильно: Итерируй по копии или в обратном порядке

for item in arr[:]:  # По копии
    arr.remove(item)

🎓 Главное запомнить

✅ Массив = быстрый доступ O(1), но фиксированный размер ✅ Связанный список = динамический размер, но медленный доступ O(n)
✅ Индексация начинается с 0 в большинстве языков ✅ Big O помогает сравнивать эффективность операций

🔗 Связь с другими темами

Массивы и списки - это фундамент для:

• Стеков и очередей (урок 253) - специализированные списки
• Хэш-таблиц (урок 254) - массивы + хэширование
• Деревьев (урок 255) - узлы связанного списка с несколькими детьми
• Графов (урок 256) - списки смежности для представления связей
• Сортировки (урок 257) - все алгоритмы работают с массивами