Jaká je časová složitost operace přidání prvku na konec obousměrně spojovaného seznamu?

Časová složitost přidání prvku na konec dvousměrně vázaného seznamu závisí na tom, zda seznam obsahuje ukazatel na poslední prvek (ocas).

• Pokud je ukazatel na ocas, přidání prvku na konec probíhá za O(1), protože lze přímo přistoupit k poslednímu prvku a přidat nový za něj.

• Pokud ukazatel na ocas není, je třeba projít celý seznam od hlavy až k poslednímu prvku, což zabere O(n) času, kde n je počet prvků v seznamu.

Ve většině implementací dvousměrně vázaných seznamů se pro optimalizaci operací přidání na konec udržuje ukazatel na ocas, takže operace je obvykle považována za O(1).