Kā noteikt vienkāršas saistītas saraksta elementa ievietošanas vidū laika sarežģītību?

Elementa ievietošana vienkāršā saistītā sarakstā vidū vispirms prasaista sarakstu no sākuma līdz vajadzīgajai pozīcijai, jo vienkāršā saistītā sarakstā nav atpakaļejošu saiti vai tiešas piekļuves elementiem pēc indeksa.

Operācijas ievietošanas vidū laika sarežģītība ir O(n), kur n ir elementu skaits līdz ievietošanas pozīcijai. Tas ir saistīts ar nepieciešamību pārlūkot sarakstu līdz vēlamajam mezglam.

Paša ievietošanas process (norāžu maiņa) aizņem O(1), bet pozīcijas meklēšana — O(n), tāpēc kopējā sarežģītība ir O(n).