Каква е времевата метрика за операцията по вмъкване на елемент в централната част на двусвързания списък?

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

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

Обобщение:

• Търсене на позиция — O(n)
• Вмъкване — O(1)

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