Элементти байланышты тизмдин ортосуна кошуу убакыттык татаалдык кандай, эгерде сизде толтурулган массив болсо?

Эгерде сизде толтурулган массив бар болсо жана сиз байланыштырылган тизмектин ортосуна элемент кошкуңуз келсе, биринчи кезекте тизмектеги кошуу ордун табышыңыз керек. Байланыштуу тизмектеги элементти издөө убактысы — O(n), анткени керек болгон ордуна чейин элементтерди өтүшүңүз керек.

Орду табылгандан кийин, элементти байланыштырылган тизмекке кошуу — O(1), анткени шилтемелерди кайра багыттоо жетиштүү.

Ошентип, массивдин (индексти тез табууга жардам бере турган, бирок тизмектин түйүнүнөн эмес) болушу менен, байланыштырылган тизмектин ортосуна элемент кошуу жалпы убакыттык күрделүүлүгү — O(n), анткени түйүндү издөө — линейдүү убакыт.

Эгерде сизде байланыштырылган тизмектин түйүндөрүнө шилтемелер сакталган массив болсо (мисалы, тизмектеги элементтерге көрсөткүчтөрдүн массиви), анда кошуу O(1) убакытта ишке ашырылат, анткени керектүү түйүндү түз эле аласыз.

Мисал:

// Бизде байланыштырылган тизмек жана түйүндөрдүн массиви бар деп эсептейли
Node[] түйүндөрМассиви = ...; // байланыштырылган тизмектин түйүндөрүнүн массиви
int кошууИндекси = түйүндөрМассиви.length / 2;
Node мурдагыТүйүн = түйүндөрМассиви[кошууИндекси - 1];
Node жаңыТүйүн = new Node(маани);
жаңыТүйүн.next = мурдагыТүйүн.next;
мурдагыТүйүн.next = жаңыТүйүн;
// Кошуу O(1) убакытта аяктады

Эгерде сизде түйүндөр менен массив жок болсо, анда тизмекти керектүү орунга чейин өтүшүңүз керек — O(n).