Реализовать очередь с связанным списком; Почему бы было плохо вставить в голову и снять за хвостом?

Question

В моем учебнике, структуры данных и алгоритмы в Java, автор говорит список. Таким образом, вы снимаете с головы и вставляете в хвост.

Затем автор загадочно спрашивает: «Почему бы было плохо вставить в голову и удалять в хвост?» без предоставления ответа.

Я не вижу, в чем на самом деле есть разница. По сути, «голова» и «хвост» - это просто произвольные имена, которые мы определяем. Что было бы так плохо, если бы Enqueue () мы добавим голову и создаем ссылку на старую голову, и на Dequeue () мы взяли из хвоста и перемещаем хвост?

Какой ответ на вопрос автора?

Answer 1

В одном связанном списке каждый элемент имеет указатель на следующий элемент. Если у вас есть дополнительный указатель на хвостовой элемент, он у вас будет постоянное число операций OG, чтобы добавлять В список в хвосте: Получите указатель хвоста, добавьте элемент за хвостом, поместите этот новый элемент в качестве нового хвоста. Удаление с головы также требует постоянного количества операций: сделать вас новым предметом новым, голова, укажите на старую голову.

Однако, Удаление От хвоста требует указателя на предшественника на текущий хвост. Это заставляет вас столько операций, сколько есть элементы, а именно линейно много.

Другое решение состоит в том, чтобы использовать дважды связанный список, тогда вы можете выбрать то, что вы будете, но он использует вдвое больше памяти.

Answer 2

Удаление с головы и вставка в хвост - это постоянные операции по времени с односменным списком, предполагая указатели головы и хвоста. Вставить в хвост также постоянное время. Но удаление из хвоста означает перемещение указателя хвоста к голове, и, поскольку у вас нет указателя за спиной, вы не можете сделать это, не пройдя весь список, чтобы найти элемент до хвоста. Это делает вставку линейным временем вместо постоянной работы по времени, и поэтому это хуже.