Какова временная сложность операции вставки в список?

Временная сложность вставки в список зависит от конкретной реализации списка:

• Односвязный список:

  • Вставка в начало: O(1) - нужно только изменить указатель заголовка.
  • Вставка в конец: O(N) - нужно пройти весь список, чтобы найти последний элемент.
  • Вставка по индексу или после определенного элемента: O(N) - нужно пройти часть списка.

• Двухсвязный список:

  • Вставка в начало: O(1) - нужно изменить указатели заголовка и первого элемента.
  • Вставка в конец: O(1) - если есть указатель на хвост, или O(N), если нет.
  • Вставка