Меня попросили реализовать двусвязную очередь, но я знаю, что односвязная очередь проста, и все ее основные функции выполняются в big-Theta 1. В основном я говорю о реализации FIFO (не включая специальные очереди, такие как deque).
Я видел, как другие люди реализуют очередь с использованием реализации с двойной связью, и я знаю, что это требует больше памяти, поскольку для каждого узла требуется 2 указателя (предыдущий и следующий).
Есть ли преимущество двусвязной очереди перед односвязной?!
Преимущество состоит в том, что вы можете выполнять итерацию в любом направлении в двусвязном списке. Кроме того, если объекты данных имеют большой размер, дополнительные накладные расходы на память невелики.
Вам не нужен двойной LL вместо двухстороннего LL. Двустороннего LL (имеющего указатель на голову и хвост) достаточно.
Для FIFO основными операциями являются постановка в очередь и удаление из очереди. В терминах связанных списков это add_to_end и remove_from_front. Обе они являются операциями O (1) с двусторонним связанным списком.
Если вам нужна структура данных, которая может работать и как очередь, и как стек, вам понадобится двусвязный список для выполнения операций O(1). Основная операция, которая потребовала бы O(n) без двусвязного списка, — это remove_from_end/pop. Причина этого в том, что вам нужно будет найти узел, предшествующий последнему (узел 3 в примере ниже), установить его в конец, а затем удалить его указатель на узел, который вы удаляете. С двойным LL найти этот узел так же просто, как tail.prev; однако с двусторонним LL вам придется выполнить обход O (n), чтобы найти этот узел.
Первые 1 - 2 - 3 - 4 Последние
def remove_from_end():
# get node4 and remove node4 from being the tail. O(1) time as you have a pointer to the tail in a double ended LL.
# set tail node3 and remove the .next from node3 to node4. If you don't have .prev on node4, then it would take O(n) to find node3
