📊 Связные списки (Linked Lists)

Где применяются:

1. Редакторы текста и кода - реализация undo/redo функциональности
2. Музыкальные плейлисты - последовательное воспроизведение треков
3. История браузера - навигация вперед/назад
4. Файловые системы - организация каталогов и файлов
5. Карточные игры - колода карт, сброс, взятие карт

Практический пример: Система управления задачами

class Task:
    def __init__(self, name, priority):
        self.name = name
        self.priority = priority
        self.next = None

class TaskManager:
    def __init__(self):
        self.head = None
    
    def add_task(self, name, priority):
        """Добавление задачи с приоритетом"""
        new_task = Task(name, priority)
        
        if not self.head or priority > self.head.priority:
            new_task.next = self.head
            self.head = new_task
        else:
            current = self.head
            while current.next and priority <= current.next.priority:
                current = current.next
            new_task.next = current.next
            current.next = new_task
    
    def complete_task(self):
        """Выполнение самой приоритетной задачи"""
        if self.head:
            task = self.head.name
            self.head = self.head.next
            return task
        return None

🥞 Стеки (Stacks)

Где применяются:

1. Системы отмены действий (Ctrl+Z)
2. Парсеры и компиляторы - проверка скобок, преобразование выражений
3. Веб-браузеры - история посещений (кнопка "Назад")
4. Рекурсивные алгоритмы - хранение вызовов функций
5. Алгоритмы поиска - DFS в графах

Практический пример: Валидатор HTML-тегов

def validate_html(html):
    """Проверка правильности вложенности HTML-тегов"""
    stack = []
    i = 0
    
    while i < len(html):
        if html[i] == '<':
            # Закрывающий тег
            if html[i+1] == '/':
                end = html.find('>', i)
                tag = html[i+2:end]
                
                if not stack or stack.pop() != tag:
                    return False, f"Ошибка: тег </{tag}> не закрывает открытый тег"
            
            # Открывающий тег (пропускаем самозакрывающиеся)
            elif html[i+1] not in ['!', '?', '/']:
                end = html.find('>', i)
                tag = html[i+1:end].split()[0]  # Берем только имя тега
                
                if tag not in ['br', 'img', 'hr', 'input', 'meta', 'link']:
                    stack.append(tag)
            
            i = end
        i += 1
    
    return len(stack) == 0, stack

# Использование
html = "<div><p>Текст</p><span>Еще текст</span></div>"
valid, errors = validate_html(html)

🎯 Очереди (Queues)

Где применяются:

1. Системы обработки заказов - FIFO (First In, First Out)
2. Печать документов - очередь на печать
3. Колл-центры - распределение звонков
4. Симуляторы - моделирование процессов
5. Кеширование - LRU (Least Recently Used) Cache

Практический пример: Система тикетов поддержки

from datetime import datetime
from collections import deque

class SupportTicket:
    def __init__(self, user_id, issue, priority=1):
        self.user_id = user_id
        self.issue = issue
        self.priority = priority  # 1-высокий, 5-низкий
        self.created_at = datetime.now()
        self.served_at = None

class SupportSystem:
    def __init__(self):
        self.high_priority = deque()  # Приоритет 1-2
        self.normal_queue = deque()   # Приоритет 3-5
        self.serving = None
    
    def new_ticket(self, user_id, issue, priority=3):
        ticket = SupportTicket(user_id, issue, priority)
        
        if priority <= 2:
            self.high_priority.append(ticket)
        else:
            self.normal_queue.append(ticket)
        
        return ticket
    
    def serve_next(self):
        """Обслуживание следующего тикета"""
        if self.high_priority:
            ticket = self.high_priority.popleft()
        elif self.normal_queue:
            ticket = self.normal_queue.popleft()
        else:
            return None
        
        ticket.served_at = datetime.now()
        self.serving = ticket
        return ticket
    
    def average_wait_time(self):
        """Среднее время ожидания"""
        # Расчет статистики
        pass

🌳 Деревья (Trees)

Где применяются:

1. Базы данных - B-деревья для индексов
2. Файловые системы - иерархия каталогов
3. ИИ и игры - деревья решений, минимакс
4. Сжатие данных - деревья Хаффмана
5. DOM в браузерах - структура HTML-документов

Практический пример: Система рекомендаций на дереве решений

class DecisionNode:
    def __init__(self, question, true_branch, false_branch):
        self.question = question  # Вопрос/признак
        self.true_branch = true_branch  # Да
        self.false_branch = false_branch  # Нет

class Leaf:
    def __init__(self, predictions):
        self.predictions = predictions  # Прогнозы

def classify(observation, node):
    """Классификация нового наблюдения"""
    if isinstance(node, Leaf):
        return node.predictions
    
    if node.question.match(observation):
        return classify(observation, node.true_branch)
    else:
        return classify(observation, node.false_branch)

# Пример дерева для рекомендации фильма
movie_tree = DecisionNode(
    question="Нравится боевики?",
    true_branch=DecisionNode(
        question="Любит комедии?",
        true_branch=Leaf(["Миссия невыполнима", "Мстители"]),
        false_branch=Leaf(["Джон Уик", "Терминатор"])
    ),
    false_branch=DecisionNode(
        question="Любит драмы?",
        true_branch=Leaf(["Форрест Гамп", "Зеленая книга"]),
        false_branch=Leaf(["Начало", "Интерстеллар"])
    )
)

🕸️ Графы (Graphs)

Где применяются:

1. Социальные сети - связи между пользователями
2. Навигационные системы - карты и маршруты
3. Рекомендательные системы - связи между товарами
4. Сети доставки - логистика и оптимизация
5. Веб-краулеры - связи между страницами

Практический пример: Поиск кратчайшего пути для доставки

import heapq
from collections import defaultdict

class DeliveryNetwork:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_route(self, point_a, point_b, distance, traffic=1):
        """Добавление маршрута с учетом трафика"""
        actual_time = distance * traffic
        self.graph[point_a].append((point_b, actual_time))
        self.graph[point_b].append((point_a, actual_time))
    
    def shortest_path(self, start, end):
        """Алгоритм Дейкстры для поиска кратчайшего пути"""
        distances = {node: float('inf') for node in self.graph}
        distances[start] = 0
        previous = {}
        pq = [(0, start)]
        
        while pq:
            current_dist, current = heapq.heappop(pq)
            
            if current == end:
                path = []
                while current in previous:
                    path.append(current)
                    current = previous[current]
                path.append(start)
                return path[::-1], current_dist
            
            for neighbor, weight in self.graph[current]:
                distance = current_dist + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current
                    heapq.heappush(pq, (distance, neighbor))
        
        return None, float('inf')

# Использование
network = DeliveryNetwork()
network.add_route("Склад", "ТЦ", 10, 1.2)
network.add_route("Склад", "Офис", 8, 1.5)
network.add_route("Офис", "ТЦ", 5, 1.0)

path, time = network.shortest_path("Склад", "ТЦ")
print(f"Путь: {' -> '.join(path)}, Время: {time} мин")

⚡ Кучи (Heaps)

Где применяются:

1. Планировщики задач - приоритетное выполнение
2. Медианные фильтры - обработка сигналов
3. Системы реального времени - обработка событий
4. Алгоритмы сжатия - кодирование Хаффмана
5. Поиск k-го элемента - статистические расчеты

Практический пример: Система мониторинга серверов

import heapq
from datetime import datetime

class Alert:
    def __init__(self, server_id, severity, message):
        self.server_id = server_id
        self.severity = severity  # 1-критично, 5-инфо
        self.message = message
        self.timestamp = datetime.now()
    
    def __lt__(self, other):
        # Сравнение по приоритету (меньше = выше приоритет)
        if self.severity == other.severity:
            return self.timestamp < other.timestamp
        return self.severity < other.severity

class MonitoringSystem:
    def __init__(self):
        self.alerts = []
        self.resolved = []
    
    def add_alert(self, server_id, severity, message):
        alert = Alert(server_id, severity, message)
        heapq.heappush(self.alerts, alert)
        print(f"⚠️  Новое оповещение: {message}")
    
    def handle_critical(self):
        """Обработка критических оповещений"""
        if self.alerts and self.alerts[0].severity <= 2:
            alert = heapq.heappop(self.alerts)
            self.resolved.append(alert)
            print(f"🚨 Обработано критическое: {alert.message}")
            return alert
        return None
    
    def get_summary(self):
        """Статистика оповещений"""
        return {
            'critical': sum(1 for a in self.alerts if a.severity <= 2),
            'total_pending': len(self.alerts),
            'total_resolved': len(self.resolved)
        }

🔑 Хеш-таблицы (Hash Tables)

Где применяются:

1. Базы данных - индексы и быстрый поиск
2. Кеширование - кеш веб-серверов (Redis, Memcached)
3. Компиляторы - таблицы символов
4. Блокчейн - хранение транзакций
5. Словари и множества - в Python реализованы через хеш-таблицы

Практический пример: Кеш для API запросов

import time
from functools import wraps

class APICache:
    def __init__(self, ttl=300):  # TTL = 5 минут
        self.cache = {}
        self.ttl = ttl
    
    def get(self, key):
        if key in self.cache:
            value, timestamp = self.cache[key]
            if time.time() - timestamp < self.ttl:
                return value
            else:
                del self.cache[key]  # Удаляем просроченный
        return None
    
    def set(self, key, value):
        self.cache[key] = (value, time.time())
    
    def clear_expired(self):
        """Очистка просроченных записей"""
        current_time = time.time()
        expired = [k for k, (_, t) in self.cache.items() 
                  if current_time - t >= self.ttl]
        for key in expired:
            del self.cache[key]
        return len(expired)

# Декоратор для кеширования
def cached_api_call(ttl=300):
    cache = APICache(ttl)
    
    def decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            # Создаем ключ из аргументов
            key = f"{func.__name__}:{str(args)}:{str(kwargs)}"
            
            # Пробуем получить из кеша
            cached_result = cache.get(key)
            if cached_result is not None:
                print(f"📦 Данные из кеша: {key}")
                return cached_result
            
            # Выполняем запрос
            result = func(*args, **kwargs)
            cache.set(key, result)
            print(f"🌐 Новый запрос: {key}")
            
            return result
        return wrapper
    return decorator

# Использование
@cached_api_call(ttl=60)
def get_weather(city):
    # Имитация API запроса
    time.sleep(2)  # Долгий запрос
    return {"city": city, "temp": 25, "humidity": 60}

# Первый вызов - выполнит запрос
print(get_weather("Москва"))
# Второй вызов (в течение 60 сек) - вернет из кеша
print(get_weather("Москва"))

🎯 Ключевые принципы выбора структуры данных:

Выбирайте структуру по задаче:

Задача	Лучшая структура	Почему
Быстрый поиск по ключу	Хеш-таблица	O(1) в среднем
Отсортированные данные	Дерево поиска	O(log n) доступ
Очередь задач	Очередь/Куча	FIFO/Приоритет
Отмена действий	Стек	LIFO
Социальные связи	Граф	Естественное представление
Иерархические данные	Дерево	Родитель-потомок

Производительность операций:

Связный список:
  - Вставка в начало/конец: O(1)
  - Поиск: O(n)
  - Удаление из начала: O(1)

Массив/Список:
  - Доступ по индексу: O(1)
  - Поиск: O(n)
  - Вставка в конец: O(1)
  - Вставка в начало: O(n)

Хеш-таблица:
  - Вставка: O(1) в среднем
  - Поиск: O(1) в среднем
  - Удаление: O(1) в среднем

Бинарное дерево поиска:
  - Вставка: O(log n) в сбалансированном
  - Поиск: O(log n) в сбалансированном
  - Удаление: O(log n) в сбалансированном

Память и кеш-локальность:

• Массивы - лучше для кеша (данные рядом в памяти)
• Списки - динамичнее, но хуже для кеша
• Деревья - баланс между гибкостью и производительностью

🔧 Рекомендации по применению:

1. Начинайте с простых структур (списки, словари Python)
2. Профилируйте код перед оптимизацией
3. Используйте стандартные библиотеки (collections, heapq, bisect)
4. Для графовых задач - используйте NetworkX
5. Для продвинутых деревьев - рассмотрите специализированные библиотеки

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