Jaka jest złożoność czasowa wstawiania elementu do środka listy powiązanej, jeśli masz już wypełnioną tablicę?

Jeśli masz pełną tablicę i chcesz wstawić element w środek listy powiązanej, najpierw musisz znaleźć pozycję wstawienia na liście. Złożoność czasowa wyszukiwania elementu na liście powiązanej to O(n), ponieważ musisz przejść przez elementy do żądanej pozycji.

Po znalezieniu pozycji, wstawianie elementu do listy powiązanej odbywa się w O(1), ponieważ wystarczy przekierować odnośniki.

W związku z tym, całkowita złożoność czasowa wstawiania elementu w środek listy powiązanej przy użyciu tablicy (która może pomóc szybko znaleźć indeks, ale nie węzeł listy) będzie O(n), ponieważ wyszukiwanie węzła zajmuje czas liniowy.

Jeśli masz tablicę, która przechowuje odwołania do węzłów listy powiązanej (np. tablicę wskaźników na elementy listy), wtedy wstawianie może być wykonane w O(1), ponieważ od razu otrzymujesz potrzebny węzeł.

Przykład:

// Załóżmy, że mamy listę powiązaną i tablicę węzłów
Node[] tablicaWęzłów = ...; // tablica węzłów listy powiązanej
int indeksWstawienia = tablicaWęzłów.length / 2;
Node węzełPrzed = tablicaWęzłów[indeksWstawienia - 1];
Node nowyWęzeł = new Node(wartość);
nowyWęzeł.next = węzełPrzed.next;
węzełPrzed.next = nowyWęzeł;
// Wstawienie wykonano w O(1)

Jeśli nie masz tablicy z węzłami, musisz przejść przez listę do żądanej pozycji — O(n).