Wie ist die zeitliche Komplexität der Operation zum Hinzufügen eines Elements am Ende einer doppelt verketteten Liste?

Die zeitliche Komplexität beim Hinzufügen eines Elements ans Ende einer doppelt verketteten Liste hängt davon ab, ob die Liste einen Zeiger auf das letzte Element (Schwanz) hat.

• Wenn ein Zeiger auf den Schwanz vorhanden ist, erfolgt das Hinzufügen am Ende in O(1), da direkt auf das letzte Element zugegriffen und das Neue danach eingefügt werden kann.

• Wenn kein Zeiger auf den Schwanz vorhanden ist, muss die gesamte Liste vom Kopf bis zum letzten Element durchlaufen werden, was O(n) Zeit in Anspruch nimmt, wobei n die Anzahl der Elemente in der Liste ist.

In den meisten Implementierungen von doppelt verketteten Listen wird zur Optimierung der Operationen am Ende ein Zeiger auf den Schwanz gehalten, sodass die Operation in der Regel als O(1) gilt.