Jaka jest złożoność czasowa operacji wstawiania, usuwania i wyszukiwania elementów na jednokierunkowej liście?

W jednokierunkowej liście operacje mają następujące złożoności czasowe:

• Wstawianie:

  • Na początku listy — O(1), ponieważ wystarczy zmienić wskaźnik głowy.
  • Na końcu lub w dowolnym miejscu — O(n), ponieważ trzeba przejść przez listę do żądanej pozycji.

• Usuwanie:

  • Usunięcie pierwszego elementu — O(1).
  • Usunięcie elementu według wartości lub pozycji — O(n), ponieważ trzeba znaleźć element i poprzedni węzeł.

• Szukanie:

  • Szukanie elementu według wartości — O(n), ponieważ trzeba przejść przez listę sekwencyjnie.

W związku z tym operacje wstawiania i usuwania na początku listy są bardzo szybkie, podczas gdy pozostałe wymagają czasu liniowego z powodu konieczności przejścia przez listę.