Реализовать очередь с связанным списком; Почему бы было плохо вставить в голову и снять за хвостом?
-
16-10-2019 - |
Вопрос
В моем учебнике, структуры данных и алгоритмы в Java, автор говорит список. Таким образом, вы снимаете с головы и вставляете в хвост.
Затем автор загадочно спрашивает: «Почему бы было плохо вставить в голову и удалять в хвост?» без предоставления ответа.
Я не вижу, в чем на самом деле есть разница. По сути, «голова» и «хвост» - это просто произвольные имена, которые мы определяем. Что было бы так плохо, если бы Enqueue () мы добавим голову и создаем ссылку на старую голову, и на Dequeue () мы взяли из хвоста и перемещаем хвост?
Какой ответ на вопрос автора?
Решение
В одном связанном списке каждый элемент имеет указатель на следующий элемент. Если у вас есть дополнительный указатель на хвостовой элемент, он у вас будет постоянное число операций OG, чтобы добавлять В список в хвосте: Получите указатель хвоста, добавьте элемент за хвостом, поместите этот новый элемент в качестве нового хвоста. Удаление с головы также требует постоянного количества операций: сделать вас новым предметом новым, голова, укажите на старую голову.
Однако, Удаление От хвоста требует указателя на предшественника на текущий хвост. Это заставляет вас столько операций, сколько есть элементы, а именно линейно много.
Другое решение состоит в том, чтобы использовать дважды связанный список, тогда вы можете выбрать то, что вы будете, но он использует вдвое больше памяти.
Другие советы
Удаление с головы и вставка в хвост - это постоянные операции по времени с односменным списком, предполагая указатели головы и хвоста. Вставить в хвост также постоянное время. Но удаление из хвоста означает перемещение указателя хвоста к голове, и, поскольку у вас нет указателя за спиной, вы не можете сделать это, не пройдя весь список, чтобы найти элемент до хвоста. Это делает вставку линейным временем вместо постоянной работы по времени, и поэтому это хуже.