Implementieren Sie die Warteschlange mit einer verknüpften Liste; Warum sollte es schlecht sein, am Kopf auf den Kopf einzulegen und am Schwanz zu entfernen?

Question

In meinem Lehrbuch, Datenstrukturen und Algorithmen in Java, sagt der Autor, wenn Sie eine Warteschlange mithilfe einer verknüpften Liste implementieren Die Liste. Auf diese Weise entfernen Sie vom Kopf und setzen Sie am Schwanz ein.

Der Autor fragt dann kryptisch: "Warum sollte es schlecht sein, am Kopf einzulegen und am Schwanz zu entfernen?" ohne eine Antwort zu geben.

Ich kann nicht sehen, was der Unterschied wirklich ist. Tatsächlich sind "Kopf" und "Schwanz" nur willkürliche Namen, die wir definieren. Was wäre so schlimm, wenn wir einen Kopf hinzufügen und einen Verweis auf den alten Kopf erstellen und auf Dequeue () aus dem Schwanz nehmen und den Schwanz umziehen?

Was ist die Antwort auf die Frage des Autors?

Answer 1

In einer einzigen verknüpften Liste hat jedes Element einen Zeiger auf das nächste Element. Wenn Sie einen zusätzlichen Zeiger auf das Schwanzelement haben, benötigen Sie eine konstante Anzahl von OG -Operationen zu hinzufügen Zur Liste am Schwanz: Holen Sie sich den Schwanzzeiger, fügen Sie ein Element nach dem Schwanz hinzu, geben Sie dieses neue Element als neuer Schwanz ein. Das Entfernen aus dem Kopf erfordert auch eine konstante Anzahl von Operationen: Machen Sie einen neuen Artikel neu, Kopf, Punkt zum alten Kopf.

Jedoch, Entfernen vom Schwanz verlangt ein Zeiger auf den Vorgänger auf den aktuellen Schwanz. Dies erfordert so viele Operationen wie Elemente, nämlich linear viele.

Eine andere Lösung besteht darin, eine doppelt verknüpfte Liste zu verwenden, dann können Sie auswählen, was Sie wollen, aber es verwendet doppelt so viel Speicher.

Answer 2

Das Entfernen vom Kopf und das Einsetzen am Schwanz sind beide konstante Zeitoperationen mit einer einzig verknüpften Liste unter der Annahme von Kopf- und Schwanzzeiger. Das Einsetzen am Schwanz ist ebenfalls eine konstante Zeit. Wenn Sie jedoch vom Schwanz entfernt werden, können Sie den Schwanzzeiger auf den Kopf zu bewegen. Da Sie keinen Rückenzeiger haben, können Sie das nicht tun, ohne die gesamte Liste zu durchqueren, um das Element vor dem Schwanz zu finden. Dies macht das Einsetzen zu einer linearen Zeit anstelle einer ständigen Zeitoperation und deshalb ist es schlimmer.