Чӣ гуна вақт барои илова кардани унсур дар маркази рӯйхати пайвастшуда, агар шумо аллакай массиви пурра дошта бошед?

Агар шумо пурра массив дошта бошед ва хоҳед, ки унсурро дар миёнаи рӯйхати пайвастшуда ҷойгир кунед, аввал бояд ҷойгиршавии воридро дар рӯйхат ёбед. Мушкилоти вақт барои ҷустуҷӯи унсур дар рӯйхати пайвастшуда O(n) аст, зеро бояд ба унсурҳо то ҷойи лозим гузашта бошед.

Пас аз ёфтани ҷой, ворид кардани унсур дар рӯйхати пайвастшуда дар O(1) сурат мегирад, зеро ки танҳо пайвандҳоро тағир додан кофист.

Бинобар ин, умумии мушкилоти вақт барои ворид кардани унсур дар миёнаи рӯйхати пайвастшуда, бо вуҷуди вуҷуд доштани массив (ки метавонад кӯмак кунад, ки суроғаи индексро зуд пайдо кунед, аммо на узели рӯйхатро), O(n) хоҳад буд, зеро ҷустуҷӯи узел вақт мегирад.

Агар массиве дошта бошед, ки истинодҳоро ба узелҳои рӯйхати пайвастшуда нигоҳ медорад (масалан, массив ишораҳо ба унсурҳои рӯйхат), пас ворид кардан метавонад дар O(1) иҷро шавад, зеро шумо мустақиман узели заруриро мегиред.

Масалан:

// Бигзор, ки мо рӯйхати пайвастшуда ва массиви узелҳоро дорем
Node[] массивУзлов = ...; // массив узелҳои рӯйхати пайвастшуда
int индексВорид = массивУзлов.length / 2;
Node пешиУзел = массивУзлов[индексВорид - 1];
Node навУзел = new Node(қимат);
навУзел.next = пешиУзел.next;
пешиУзел.next = навУзел;
// Ворид кардан дар O(1) анҷом ёфт

Агар массиви бо узелҳо надошта бошед, пас бояд то ҷойи лозим рӯйхатро гузаред — O(n).