Связные списки служат универсальным инструментом, предоставляющим гибкую основу для создания различных структур данных. Эта гибкость позволяет реализовывать фундаментальные абстракции, такие как стек и очередь. То есть связные списки — это «строительный материал», а стек и очередь — «конструкции», которые можно построить на его основе.
Стек (LIFO) работает по принципу «последним пришёл — первым вышел».
При реализации стека на основе связного списка добавление и удаление элементов происходит с одного конца — головы списка. Каждая операция push создаёт новый узел и помещает его в начало списка, а pop удаляет головной элемент. Это обеспечивает константную сложность O(1) для основных операций.
Очередь (FIFO) работает по правилу «первым пришёл — первым вышел».
В связном списке добавление элемента происходит в конец списка (tail), а извлечение — из начала (head). Для эффективной реализации необходимо поддерживать ссылки на оба конца списка. Это позволяет выполнять операции enqueue и dequeue за постоянное время O(1).
