Aká je časová zložitosť pri vykonávaní operácií vkladania, odstraňovania a vyhľadávania prvkov v jednoduchej spájanej listine?

V jednoduchej spájanej zozname majú operácie nasledujúcu časovú zložitosť:

• Vkladanie:

  • Na začiatok zoznamu — O(1), pretože stačí zmeniť ukazovateľ hlavy.
  • Na koniec alebo na ľubovoľné miesto — O(n), pretože je potrebné prejsť zoznam až na požadovanú pozíciu.

• Odstraňovanie:

  • Odstránenie prvého prvku — O(1).
  • Odstránenie prvku podľa hodnoty alebo pozície — O(n), pretože je potrebné nájsť prvok a predchádzajúci uzol.

• Vyhľadávanie:

  • Vyhľadávanie prvku podľa hodnoty — O(n), pretože je potrebné prejsť zoznam sekvenčne.

Týmto sú operácie vkladania a odstraňovania na začiatku zoznamu veľmi rýchle, zatiaľ čo ostatné vyžadujú lineárny čas kvôli potrebe prejsť zoznam.