Приведи пример задачи, где требуется односвязный список

Практические примеры использования односвязных списков

Односвязный список (singly linked list) — это структура данных, где каждый узел содержит значение и ссылку на следующий узел. Хотя встроенные структуры Python часто предпочтительнее, есть реальные задачи, где односвязный список имеет смысл.

Пример 1: Навигация истории браузера (Back button)

Это классический пример, где требуется стек с быстрым добавлением и удалением элементов:

class HistoryNode:
    def __init__(self, url: str):
        self.url = url
        self.next = None

class BrowserHistory:
    def __init__(self):
        self.current = None
    
    def visit(self, url: str):
        """Посещаем новую страницу (добавляем в начало)"""
        new_node = HistoryNode(url)
        new_node.next = self.current
        self.current = new_node
        print(f"Visiting: {url}")
    
    def back(self) -> bool:
        """Возвращаемся на предыдущую страницу"""
        if self.current and self.current.next:
            self.current = self.current.next
            print(f"Going back to: {self.current.url}")
            return True
        return False
    
    def get_current(self) -> str:
        return self.current.url if self.current else None

# Использование
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("stackoverflow.com")
browser.visit("github.com")
print(browser.get_current())  # github.com
browser.back()
print(browser.get_current())  # stackoverflow.com

Почему односвязный список?

• Добавление нового элемента O(1)
• Удаление элемента O(1)
• Не нужен доступ в обе стороны
• Экономия памяти (одна ссылка вместо двух)

Пример 2: Реализация стека (Stack)

Односвязный список идеален для стека благодаря структуре LIFO:

class StackNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
    
    def push(self, data) -> None:
        """Добавляем элемент в стек O(1)"""
        new_node = StackNode(data)
        new_node.next = self.top
        self.top = new_node
        self.size += 1
    
    def pop(self):
        """Удаляем элемент из стека O(1)"""
        if self.is_empty():
            return None
        data = self.top.data
        self.top = self.top.next
        self.size -= 1
        return data
    
    def peek(self):
        """Смотрим верхний элемент без удаления"""
        return self.top.data if self.top else None
    
    def is_empty(self) -> bool:
        return self.size == 0
    
    def __len__(self) -> int:
        return self.size

# Использование: проверка сбалансированных скобок
def is_balanced_parentheses(expression: str) -> bool:
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in expression:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    
    return stack.is_empty()

print(is_balanced_parentheses("({[]})"))  # True
print(is_balanced_parentheses("({[}])"))  # False

Пример 3: Реализация очереди (Queue)

Односвязный список подходит для очереди, если добавляем в конец и удаляем из начала:

class QueueNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0
    
    def enqueue(self, data) -> None:
        """Добавляем элемент в конец O(1)"""
        new_node = QueueNode(data)
        if self.is_empty():
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1
    
    def dequeue(self):
        """Удаляем элемент с начала O(1)"""
        if self.is_empty():
            return None
        data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        self.size -= 1
        return data
    
    def is_empty(self) -> bool:
        return self.size == 0

# Использование: обработка задач в порядке очереди
class TaskQueue:
    def __init__(self):
        self.queue = Queue()
    
    def add_task(self, task: str):
        self.queue.enqueue(task)
        print(f"Task added: {task}")
    
    def process_tasks(self):
        while not self.queue.is_empty():
            task = self.queue.dequeue()
            print(f"Processing: {task}")

processor = TaskQueue()
processor.add_task("Send email")
processor.add_task("Generate report")
processor.add_task("Upload data")
processor.process_tasks()
# Processing: Send email
# Processing: Generate report
# Processing: Upload data

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

Односвязный список хорош для представления полинома:

class Term:
    def __init__(self, coefficient: float, exponent: int):
        self.coeff = coefficient
        self.exp = exponent
        self.next = None

class Polynomial:
    def __init__(self):
        self.head = None
    
    def add_term(self, coeff: float, exp: int):
        """Добавляем элемент с сохранением порядка"""
        new_term = Term(coeff, exp)
        
        if not self.head:
            self.head = new_term
            return
        
        # Находим правильную позицию (по убыванию экспоненты)
        if new_term.exp > self.head.exp:
            new_term.next = self.head
            self.head = new_term
            return
        
        current = self.head
        while current.next and current.next.exp > new_term.exp:
            current = current.next
        
        new_term.next = current.next
        current.next = new_term
    
    def evaluate(self, x: float) -> float:
        """Вычисляем значение полинома"""
        result = 0
        current = self.head
        while current:
            result += current.coeff * (x ** current.exp)
            current = current.next
        return result
    
    def __str__(self) -> str:
        """Красивый вывод полинома"""
        terms = []
        current = self.head
        while current:
            if current.exp == 0:
                terms.append(f"{current.coeff}")
            elif current.exp == 1:
                terms.append(f"{current.coeff}x")
            else:
                terms.append(f"{current.coeff}x^{current.exp}")
            current = current.next
        return " + ".join(terms)

# Использование: 3x^2 + 2x + 5
poly = Polynomial()
poly.add_term(3, 2)
poly.add_term(2, 1)
poly.add_term(5, 0)
print(poly)  # 3x^2 + 2x + 5
print(poly.evaluate(2))  # 3*4 + 2*2 + 5 = 21

Пример 5: Чередование двух списков (Merge sorted lists)

Типичная задача на собеседованиях — слияние двух отсортированных списков:

class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next = None

def merge_sorted_lists(list1: ListNode, list2: ListNode) -> ListNode:
    """Объединяем два отсортированных списка O(n+m)"""
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # Присоединяем оставшиеся элементы
    current.next = list1 if list1 else list2
    
    return dummy.next

# Использование
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(4)

list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)

merged = merge_sorted_lists(list1, list2)

# Вывод результата
current = merged
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None")  # 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None

Пример 6: Обнаружение цикла (Cycle detection)

Задача на алгоритм Floyd (черепаха и заяц):

def has_cycle(head: ListNode) -> bool:
    """Проверяем наличие цикла O(n) времени, O(1) памяти"""
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    
    return False

def find_cycle_start(head: ListNode) -> ListNode:
    """Находим начало цикла"""
    slow = head
    fast = head
    
    # Находим точку встречи
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # Цикла нет
    
    # Находим начало цикла
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

# Использование
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Цикл

print(has_cycle(node1))  # True
print(find_cycle_start(node1).val)  # 2

Когда использовать односвязный список?

Вывод

Односвязный список полезен в конкретных сценариях:

1. Стеки и очереди — где O(1) операции критичны
2. Истории и навигация — браузер, undo-redo
3. Потоковые данные — обработка потока по FIFO
4. Структурированные данные — полиномы, графы
5. Собеседования — требуется знание структуры

Для повседневной работы в Python часто лучше использовать list или collections.deque, но понимание односвязного списка критично для интервью и алгоритмического мышления.