Jak ocenić złożoność czasową operacji wstawiania, usuwania i wyszukiwania elementów na liście powiązanej?

Złożoność czasowa operacji na liście powiązanej zależy od tego, co dokładnie robimy i czy mamy dostęp do potrzebnego elementu:

• Wstawianie:

  • Na początku listy — O(1), ponieważ wystarczy zmienić odwołania.
  • Na końcu listy jednokierunkowej bez wskaźnika na koniec — O(n), trzeba przejść całą listę.
  • Na końcu z wskaźnikiem na koniec — O(1).
  • W dowolnym miejscu (według indeksu lub wartości) — O(n), ponieważ trzeba znaleźć pozycję.

• Usuwanie:

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

• Wyszukiwanie:

  • Szukanie elementu po wartości — O(n), ponieważ trzeba przejść listę.

W związku z tym główne operacje wymagają czasu liniowego, jeśli nie mamy bezpośredniego dostępu do potrzebnego węzła. Wynika to z sekwencyjnej natury list powiązanych.