Jaká je časová složitost vložení prvku do středu spojovaného seznamu, pokud již máte zaplněný pole?

Pokud máte zaplněný pole a chcete vložit prvek doprostřed spojovaného seznamu, nejprve musíte najít pozici vložení v seznamu. Časová složitost hledání prvku v spojovaném seznamu je O(n), protože musíte projít prvky až na požadovanou pozici.

Po nalezení pozice se vložení prvku do spojovaného seznamu provádí v O(1), protože stačí přesměrovat odkazy.

Celková časová složitost vložení prvku do středu spojovaného seznamu při existenci pole (které může pomoci rychle najít index, ale ne uzel seznamu) bude O(n), protože hledání uzlu trvá lineární čas.

Pokud máte pole, které uchovává odkazy na uzly spojovaného seznamu (například pole ukazatelů na prvky seznamu), pak může být vložení provedeno v O(1), protože ihned získáte potřebný uzel.

Příklad:

// Předpokládejme, že máme spojovaný seznam a pole uzlů
Node[] poleUzlů = ...; // pole uzlů spojovaného seznamu
int indexVlozeni = poleUzlů.length / 2;
Node predchoziUzel = poleUzlů[indexVlozeni - 1];
Node novyUzel = new Node(hodnota);
novyUzel.next = predchoziUzel.next;
predchoziUzel.next = novyUzel;
// Vložení bylo provedeno v O(1)

Pokud nemáte pole s uzly, musíte projít seznam až na požadovanou pozici — O(n).