Zeitaufwand für Operationen bei der Implementierung von Stack und Queue

Question

Ich untersuche Datenstrukturen und habe Zweifel an der zeitlichen Komplexität in verschiedenen Implementierungen von Stacks und Queues.

Für Warteschlangen, in denen ein Element am Kopf oder am Ende in die Warteschlange eingereiht werden kann, gibt eine dynamische Array-Implementierung O (1) amortisierte Zeit für das Einfügen an Ende und Anfang. Eine Implementierung einer verknüpften Liste ergibt eine O (1) -Implementierung.

Bei Stapeln, bei denen ein Knoten am Anfang oder am Ende der Liste hinzugefügt werden kann, ergeben eine einfach verknüpfte Liste und eine Array-Implementierung eine O (1) -Häufigkeit.

Bin ich richtig oder fehle ich etwas?

Answer 1

Wenn Sie den Index für die nächste Einfügeposition beibehalten, dauert die Einfügeoperation eine bestimmte Zeit, damit O (1) korrekt ist.

Wenn jedoch keine Indizes gepflegt sind, müssen wir nach dem korrekten Ort zum Einfügen des neuen Elements suchen und die Zeit zum Einfügen dieses Elements wird linear mit der Anzahl der Elemente in der Datenstruktur zunehmen, also die Einfügezeit in dieser Fall wäre O (n)