Каква е времевата сложност при вмъкване на елемент в средата на свързан списък, ако вече имате запълнен масив?

Ако имате пълен масив и искате да вмъкнете елемент в средата на свързан списък, първо трябва да намерите позицията за вмъкване в списъка. Времевата сложност за търсене на елемент в свързан списък е O(n), тъй като трябва да преминете през елементите до желаната позиция.

След като позицията бъде намерена, вмъкването на елемента в свързания списък става за O(1), тъй като е достатъчно да пренасочите връзките.

Следователно, общата времева сложност за вмъкване на елемент в средата на свързан списък при наличие на масив (който може да помогне бързо да намерите индекса, но не и възела на списъка) ще бъде O(n), тъй като търсенето на възела отнема линейно време.

Ако имате масив, който съхранява препратки към възлите на свързания списък (например, масив от указатели към елементите на списъка), тогава вмъкването може да бъде изпълнено за O(1), тъй като получавате директно необходимия възел.

Пример:

// Да предположим, че имаме свързан списък и масив от възли
Node[] масивВъзли = ...; // масив от възли на свързания списък
int индексВмъкване = масивВъзли.length / 2;
Node предишенВъзел = масивВъзли[индексВмъкване - 1];
Node новВъзел = new Node(стойност);
новВъзел.next = предишенВъзел.next;
предишенВъзел.next = новВъзел;
// Вмъкването е извършено за O(1)

Ако нямате масив с възли, трябва да преминете през списъка до желаната позиция — O(n).