Привет! Это вторая часть из цикла статей "Ультимативный гайд по структурам данных и алгоритмам на Python" 🧠. В первой части мы заложили фундамент, разобравшись с базовыми инструментами, которые Python предоставляет "из коробки". Мы увидели их сильные стороны и "подводные камни" производительности. Теперь пора двигаться дальше и осваивать более продвинутые концепции и инструменты!
# Анти-пример: Очередь на list
print("Демонстрация проблемы с list.pop(0):")
queue_list = ['A', 'B', 'C', 'D']
print(f" Исходная очередь: {queue_list}, id: {id(queue_list)}")
# Извлекаем первый элемент (Dequeue) - O(n)!
first_item = queue_list.pop(0)
print(f" Извлекли: '{first_item}'")
print(f" Очередь после pop(0): {queue_list}, id: {id(queue_list)}")
# Заметьте, что 'B', 'C', 'D' сдвинулись на индексы 0, 1, 2!
# ID списка тот же, но внутреннее содержимое перестроено.from collections import deque
# Создаем deque
d = deque(['b', 'c', 'd'])
print(f"Исходный deque: {d}")
# Работаем с правым концом (как list)
d.append('e') # O(1)
print(f"После append('e'): {d}")
item_right = d.pop() # O(1)
print(f"После pop(): {item_right=}, deque: {d}")
# Работаем с левым концом (быстро, в отличие от list!)
d.appendleft('a') # O(1)
print(f"После appendleft('a'): {d}")
item_left = d.popleft() # O(1)
print(f"После popleft(): {item_left=}, deque: {d}")Вывод: `deque` — это не полная замена списков. Это специализированный инструмент, который очень хорош, когда вам нужны быстрые (O(1)) операции добавления/удаления с обоих концов последовательности.
from collections import deque
# Используем deque как стек для истории команд
command_history = deque()
print("Симуляция работы с текстовым редактором:")
# Пользователь выполняет действия (push через append)
action1 = "Набрать текст: 'Привет'"
command_history.append(action1)
print(f" -> Выполнено: '{action1}', Стек: {command_history}")
action2 = "Сделать текст жирным"
command_history.append(action2)
print(f" -> Выполнено: '{action2}', Стек: {command_history}")
action3 = "Добавить смайлик 😎"
command_history.append(action3)
print(f" -> Выполнено: '{action3}', Стек: {command_history}")
# Пользователь нажимает "Отмена" (pop)
print("\nНажата кнопка 'Отмена'...")
if command_history: # Проверяем, что стек не пуст
last_action = command_history.pop() # O(1)
print(f" <- Отменено действие: '{last_action}'")
print(f" Осталось в стеке: {command_history}")
else:
print("Нет действий для отмены.")
# Еще раз "Отмена"
print("\nНажата кнопка 'Отмена'...")
if command_history:
last_action = command_history.pop() # O(1)
print(f" <- Отменено действие: '{last_action}'")
print(f" Осталось в стеке: {command_history}")
else:
print("Нет действий для отмены.")from collections import deque
import time
import random
# Используем deque как очередь для заданий на печать
printer_queue = deque()
# Моделируем поступление заданий (Enqueue через append)
print("\n--- Моделирование очереди печати ---")
print("Поступают задания:")
for i in range(1, 6): # 5 заданий
job_name = f"Document_{i}.pdf"
printer_queue.append(job_name) # O(1)
print(f" [+] Поступило: '{job_name}'. Очередь: {list(printer_queue)}") # list() для наглядности
time.sleep(random.uniform(0.2, 0.5)) # Имитация паузы между заданиями
# Моделируем работу принтера (Dequeue через popleft)
print("\nПринтер начинает обработку:")
while printer_queue: # Пока очередь не пуста
current_job = printer_queue.popleft() # O(1) - Быстрое извлечение!
print(f" [*] Печатается: '{current_job}'...")
processing_time = random.uniform(0.5, 1.0) # Имитация времени печати
time.sleep(processing_time)
print(f" [✓] Готово: '{current_job}' (за {processing_time:.2f} сек). Осталось в очереди: {len(printer_queue)}")
print("\n--- Очередь печати пуста! Принтер свободен. ---")Ключевая идея: узлы не обязаны лежать в памяти рядом друг с другом. Они могут быть разбросаны где угодно. Единственное, что связывает их в последовательность — это цепочка ссылок `next`, идущая от `head` до `None`.
Итог: связанные списки — это не столько инструмент для ежедневного использования, сколько важнейший элемент образования. Это как знать основы алгебры, чтобы понимать высшую математику.
class Node:
"""
Представляет узел (звено) односвязного списка.
Хранит данные и ссылку на следующий узел.
"""
def __init__(self, data=None):
self.data = data # Данные, которые хранит узел
self.next = None # Ссылка на следующий узел, по умолчанию None
def __repr__(self):
"""Возвращает строковое представление данных узла.
Удобно при печати всего списка.
"""
return str(self.data)class LinkedList:
"""
Представляет сам односвязный список.
Хранит ссылку на голову (head) и предоставляет базовые операции.
"""
def __init__(self, nodes_data=None):
"""
Инициализирует связанный список.
Может принимать итерируемый объект (например, list, tuple)
для создания узлов списка при инициализации.
"""
self.head = None # Изначально список пуст, головы нет
if nodes_data is not None:
# Пытаемся создать список из переданных данных
try:
# Получаем итератор, чтобы работать с любым итерируемым типом
iterator = iter(nodes_data)
# Создаем голову из первого элемента
first_node_data = next(iterator)
self.head = Node(first_node_data)
current_node = self.head
# Добавляем и связываем остальные элементы
for elem_data in iterator:
current_node.next = Node(elem_data)
current_node = current_node.next # Переходим к только что созданному узлу
except StopIteration:
# Исходный итератор был пуст, self.head останется None
pass
except TypeError:
# Переданный объект неитерируемый
print("Ошибка: Для инициализации LinkedList нужны итерируемые данные.")
self.head = None # Сбрасываем на всякий случай
def __repr__(self):
"""
Возвращает человекочитаемое строковое представление всего списка.
Формат: data1 -> data2 -> ... -> None
"""
nodes_repr = []
current_node = self.head
while current_node is not None:
# Добавляем представление данных текущего узла (используя Node.__repr__)
nodes_repr.append(str(current_node))
current_node = current_node.next # Переходим к следующему узлу
nodes_repr.append("None") # Явно показываем конец списка
return " -> ".join(nodes_repr)# 1. Создание пустого списка
empty_llist = LinkedList()
print(f"Пустой список: {empty_llist}")
# 2. Создание узлов и ручное связывание
node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
# Связываем их: A -> B -> C -> None
node1.next = node2
node2.next = node3
# Создаем список и назначаем голову
manual_llist = LinkedList()
manual_llist.head = node1
print(f"Список, связанный вручную: {manual_llist}")
# 3. Создание списка из итерируемого объекта (списка Python)
auto_llist = LinkedList(['Раз', 'Два', 'Три'])
print(f"Список, созданный из list: {auto_llist}")
# 4. Создание из другого итератора (например, range)
range_llist = LinkedList(range(5))
print(f"Список, созданный из range(5): {range_llist}")
# 5. Пример с пустым итератором
empty_init_llist = LinkedList([])
print(f"Список, созданный из []: {empty_init_llist}")class Node:
""" Узел связанного списка (без изменений) """
def __init__(self, data=None):
self.data = data
self.next = None
def __repr__(self):
return str(self.data)
class LinkedList:
""" Сам связанный список """
def __init__(self, nodes_data=None):
self.head = None
# ... (код инициализации из предыдущего шага без изменений) ...
if nodes_data is not None:
try:
iterator = iter(nodes_data)
first_node_data = next(iterator)
self.head = Node(first_node_data)
current_node = self.head
for elem_data in iterator:
current_node.next = Node(elem_data)
current_node = current_node.next
except StopIteration: pass
except TypeError:
print("Ошибка: Для инициализации LinkedList нужны итерируемые данные.")
self.head = None
def __repr__(self):
""" Представление списка (без изменений) """
nodes_repr = []
current_node = self.head
while current_node is not None:
nodes_repr.append(str(current_node))
current_node = current_node.next
nodes_repr.append("None")
return " -> ".join(nodes_repr)
# !!! ВОТ ОН, НАШ ИТЕРАТОР !!!
def __iter__(self):
"""
Позволяет итерироваться по данным узлов списка
с помощью стандартного цикла for.
"""
current = self.head # Начинаем с головы
while current is not None:
yield current.data # Возвращаем данные текущего узла
current = current.next # Переходим к следующему# Создадим плейлист
my_playlist = LinkedList(["The Beatles", "Queen", "Led Zeppelin", "Pink Floyd"])
print(f"Мой плейлист: {my_playlist}")
print("\nВоспроизводим треки (итерация с помощью for):")
for track in my_playlist: # Теперь это работает благодаря __iter__!
print(f" 🎶 Сейчас играет: {track}")
# Мы можем использовать и другие конструкции, ожидающие итерируемый объект:
playlist_list = list(my_playlist) # Преобразовать в обычный список Python
print(f"\nПлейлист как Python list: {playlist_list}")
playlist_tuple = tuple(my_playlist) # Преобразовать в кортеж
print(f"Плейлист как tuple: {playlist_tuple}")
# Посчитаем длину "питоничным" способом (хотя это O(n) под капотом!)
length = len(playlist_list) # len() работает со списком, полученным из итератора
# Или можно было бы реализовать __len__ в LinkedList, который бы делал обход
print(f"Количество треков: {length}")Мой плейлист: The Beatles -> Queen -> Led Zeppelin -> Pink Floyd -> None
Воспроизводим треки (итерация с помощью for):
🎶 Сейчас играет: The Beatles
🎶 Сейчас играет: Queen
🎶 Сейчас играет: Led Zeppelin
🎶 Сейчас играет: Pink Floyd
Плейлист как Python list: ['The Beatles', 'Queen', 'Led Zeppelin', 'Pink Floyd']
Плейлист как tuple: ('The Beatles', 'Queen', 'Led Zeppelin', 'Pink Floyd')
Количество треков: 4Итог: Хотя вы не будете писать `class LinkedList` каждый день, работая на Python, потраченное время на понимание их концепции окупится сторицей. Это знание расширяет ваш кругозор, помогает глубже понять другие структуры данных и алгоритмы, а также подготовит вас к каверзным вопросам на собеседованиях. Считайте это необходимой теоретической базой для любого серьезного разработчика.
Ключевой вывод: Не существует "идеальной" структуры данных на все случаи жизни. Выбор всегда зависит от конкретной задачи и требований к производительности для разных операций. `deque` бьет `list` на операциях с начала, но проигрывает в доступе по индексу. Связанный список (теоретически) выигрывает при вставке в середину, но ужасен для поиска. Понимание этих компромиссов и внутреннего устройства — ключ к написанию по-настоящему эффективного кода.