Jak ocenia się trudność operacji wstawiania elementu do centralnej części listy dwukierunkowej?

Wstawianie elementu w środkowej części dwukierunkowej listy zazwyczaj wymaga najpierw znalezienia pozycji wstawiania, a następnie zmiany odnośników sąsiednich węzłów.

Złożoność operacji:

• Szukanie pozycji: jeśli masz odwołanie do węzła, do którego chcesz wstawić, wyszukiwanie nie jest potrzebne.
• Wstawianie: zmiana odnośników sąsiednich węzłów to operacja O(1).

Jeśli pozycja wstawiania jest określana przez indeks, trzeba przejść przez listę do żądanego węzła, co zajmuje O(n) czasu.

Podsumowując:

• Jeśli pozycja jest znana (węzeł znaleziony) — wstawianie w O(1).
• Jeśli pozycja jest określana przez indeks — wyszukiwanie + wstawianie w O(n).