Jaká je časová složitost při provádění operací vkládání, mazání a hledání prvků v jednoduše spojeném seznamu?

V jednoduchém spojovém seznamu mají operace následující časové složitosti:

• Vkládání:

  • Na začátek seznamu — O(1), protože stačí změnit ukazatel hlavy.
  • Na konec nebo na libovolné místo — O(n), protože je třeba projít seznam až na požadovanou pozici.

• Odstraňování:

  • Odstranění prvního prvku — O(1).
  • Odstranění prvku podle hodnoty nebo pozice — O(n), protože je třeba najít prvek a předchozí uzel.

• Vyhledávání:

  • Vyhledávání prvku podle hodnoty — O(n), protože je třeba projít seznam sekvenčně.

Tímto jsou operace vkládání a odstraňování na začátku seznamu velmi rychlé, zatímco ostatní vyžadují lineární čas kvůli nutnosti projít seznam.