#algorithm #data-structures #linked-list #queue
Вопрос:
Меня попросили реализовать двусвязную очередь, но я знаю, что односвязная очередь проста, все ее основные функции выполняются в big-Theta 1. Я в основном говорю о реализации FIFO (не включая специальные очереди, такие как deque).
Я видел, как другие люди реализовывали очередь, используя реализацию с двойной связью, и я знаю, что это потребляет больше памяти, поскольку для каждого узла требуется 2 указателя (предыдущий и следующий).
Есть ли какое-либо преимущество двусвязной очереди перед односвязной очередью ?!
Комментарии:
1. Вы слышали о двойной очереди? , В этом пользователю разрешено вводить и отменять с обоих концов. Это зависит от конкретного приложения.
2. Вы можете перейти по этой ссылке для того же geeksforgeeks.org/doubly-linked-list
3. Я знаю двухстороннюю очередь (deque), но меня беспокоит обычная реализация очереди FIFO @LalitVerma
4. Для обычной структуры списка всегда есть преимущества реализации двусвязного списка, но мой вопрос основан на реализации очереди, поскольку функции отличаются от списка @iwayankit
Ответ №1:
Вам не нужно двойное заполнение по сравнению с двусторонним заполнением. Достаточно двухконтурного LL (имеет указатель на head и tail).
Для FIFO основными операциями являются постановка в очередь и снятие с очереди. В терминах связанного списка это add_to_end и remove_from_front . Обе эти операции представляют собой O (1) операций с двусторонним связанным списком.
Если вам нужна структура данных, которая может работать как как очередь, так и как стек, тогда вам понадобится двусвязный список для выполнения O (1) операций. Основная операция, которая заняла бы O (n) без двусвязного списка, — это remove_from_end /pop . Причина этого в том, что вам нужно будет найти узел, предшествующий последнему (node3 в примере ниже), установить его в хвост, а затем удалить его указатель на узел, который вы удаляете. При двойном заполнении найти этот узел так же просто, как tail.prev; однако при двустороннем заполнении вам нужно будет выполнить обход 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
Комментарии:
1. Почему бы вам не использовать начало двойного конца LL в качестве открытого конца стека? С двусторонним заполнением вы можете вставлять в O (1) раз на обоих концах, а также удалять с начала в O (1)
Ответ №2:
Преимущество заключается в том, что вы можете выполнять итерации в любом направлении по двусвязному списку. Кроме того, если объекты данных являются значительными, то дополнительные затраты памяти составляют небольшой процент.
Комментарии:
1. Для обычных операций с очередью (постановка в очередь, снятие с очереди, также очистка, получение переднего / заднего значения и получение длины, пусто, заполнено и т. Д.) Им Не нужно, Чтобы вы выполняли итерации в обоих направлениях. Им даже не нужно, чтобы вы выполняли итерации в любом направлении, за исключением распечатки очереди и других второстепенных функций. Я все еще не вижу преимущества в этом @Dragonthoughts
2. Как выполнить удаление с любого конца односвязной очереди без итерации до конца с самого начала? Вам нужно знать, что указывает на ваш конец, чтобы превратить его в ваш новый конец.
3. Вот почему я включил в свой вопрос слова «основные функции» очереди. Вы говорите о специальной очереди (deque), но моя проблема в основном связана с реализацией FIFO, может быть, позвольте мне обновить мой вопрос, чтобы быть более понятным
4. Если вы создаете реализацию FIFO, вы добавляете на одном конце и удаляете из очереди на другом. Как вы поддерживаете порядок указателей, не повторяя до конца одну операцию в односвязной структуре?
5. @Dragonthoughts Что ты хочешь сделать с указателями? Мне не нужно ничего трогать в середине. Мне нужны только указатели на первый и последний элемент. Текущий последний элемент указывает на следующий, и если я удаляю его из очереди, я получаю оттуда следующий «последний» указатель. Когда я вставляю спереди, у меня тоже есть указатель на этот элемент, чтобы изменить его свойство «next» на то, которое я только что вставил. Нет необходимости выполнять итерации или касаться чего-либо промежуточного.