Jak odhadnout časovou složitost operací vkládání, odstraňování a hledání prvků v spojovaném seznamu?

Časová složitost operací v spojovaném seznamu závisí na tom, co přesně děláme, a zda máme přístup k potřebnému prvku:

• Vkládání:

  • Na začátek seznamu — O(1), protože stačí změnit odkazy.
  • Na konec jednoduše spojovaného seznamu bez ukazatele na konec — O(n), je třeba projít celý seznam.
  • Na konec s ukazatelem na konec — O(1).
  • Na libovolné místo (podle indexu nebo hodnoty) — O(n), protože je třeba najít pozici.

• Odstranění:

  • Odstranění prvního prvku — O(1).
  • Odstranění podle hodnoty nebo indexu — O(n), protože je třeba najít prvek a jeho předchůdce.

• Hledání:

  • Hledání prvku podle hodnoty — O(n), protože je třeba projít seznam.

Tímto způsobem hlavní operace vyžadují lineární čas, pokud nemáme přímý přístup k potřebnému uzlu. To je způsobeno sekvenční povahou spojovaných seznamů.