Ako odhadnúť časovú zložitosť operácií vkladania, odstraňovania a vyhľadávania prvkov v spojenom zozname?

Časová zložitosť operácií v spojenom zozname závisí od toho, čo presne robíme, a či máme prístup k potrebnému uzlu:

• Vkladanie:

  • Na začiatok zoznamu — O(1), pretože stačí zmeniť odkazy.
  • Na koniec jednoducho spojeného zoznamu bez ukazovateľa na koniec — O(n), je potrebné prejsť celý zoznam.
  • Na koniec s ukazovateľom na koniec — O(1).
  • Na ľubovoľnom mieste (podľa indexu alebo hodnoty) — O(n), pretože je potrebné nájsť pozíciu.

• Odstránenie:

  • Odstránenie prvého prvku — O(1).
  • Odstránenie podľa hodnoty alebo indexu — O(n), pretože je potrebné nájsť prvok a jeho predchodcu.

• Hľadanie:

  • Hľadanie prvku podľa hodnoty — O(n), pretože je potrebné prejsť zoznam.

Týmto spôsobom hlavné operácie vyžadujú lineárny čas, ak nemáme priame prístupy k potrebnému uzlu. To je spôsobené sekvenčnou povahou spojených zoznamov.