Zašto operacije umetanja na početak i kraj liste traju isto vreme, ne zavisno od veličine strukture?

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

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

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