Kodėl įterpimo operacijos į pradžią ir pabaigą sąrašo vykdomos vienu metu, nepriklausomai nuo struktūros dydžio?

Операции вставки в начало и в конец списка выполняются за одинаковое время, не зависящее от размера структуры, если используется связный список с указателями на голову и хвост:

• Вставка в начало: создаётся новый узел, его ссылка на следующий указывает на текущую голову, затем голова обновляется на новый узел — операция O(1).
• Вставка в конец: если есть указатель на хвост, новый узел добавляется после хвоста, затем хвост обновляется — операция O(1).

В отличие от массивов, где вставка в начало требует сдвига элементов, связный список позволяет быстро менять ссылки без перебора всех элементов.