Очередь, реализованная в виде связанного списка с временной сложностью O(n)
Как следует из названия, я хочу реализовать очередь, используя связанный список. Однако когда я пытаюсь реализовать постановку в очередь или удаление из очереди, мне приходится перемещаться по связанному списку, чтобы получить последний элемент, временная сложность которого равна O(n). С другой стороны, использование массива для реализации очереди может обеспечить временную сложность O(1). Есть ли какой-либо подход, который позволяет мне реализовать эти операции с временной сложностью O (1), возможно, с помощью другого указателя или чего-то подобного?
Могу ли я получить последний элемент с временной сложностью O (1) в связанном списке?
С нетерпением ждем вашего ответа!
Я использую язык программирования C, куда мне следует поместить указатель? в структуре или другом месте? это ключ. можешь ли ты высказать мне свою точку зрения?
Вероятно, вы где-то храните указатель на первый элемент. Поместите другой указатель рядом с ним, чтобы ему не было одиноко.
Если вы не можете заставить его работать, отредактируйте свой вопрос и добавьте минимальный код, чтобы воспроизвести проблему.
Будете ли вы публиковать свой код или ваш вопрос устарел?
Я реализовал это, используя такую структуру, как struct Queue { ptr front; ПТР задний; } }
Хорошо, вопрос можно закрыть.
Ответы 1
Рассмотрим двусвязный список, использующий один узел в качестве сторожевого узла, который не хранит данные, но указывает на начало и конец вашего списка, что делает список кольцевым. Поддерживая ссылку на дозорный узел, ваша функция постановки в очередь может добавлять новые элементы непосредственно после хвоста, а ваша функция удаления из очереди может удалять элементы непосредственно из головы. Это аккуратная реализация, в которой сторожевой узел упрощает граничные условия и обеспечивает постоянное время для обеих операций.
Именно так Visual Studio реализует C++ std::list, за исключением того, что его сторожевой узел такой же, как и узлы std::list, и устанавливает данные в ноль или нуль.
большое спасибо, похоже, это способ реализации очереди по массиву. он также использует круговой массив для реализации очереди.
Круто :) На GeeksForGeeks есть подробная статья с реализацией. Если вы нашли это полезным, рассмотрите возможность принятия ответа :)
Сохраните указатель (ссылку или что-то еще, что есть в вашем языке) на последний элемент в переменной, тогда вы сможете получить последний элемент в O (1). Это вполне возможно, дерзайте.