Какова временная сложность операции добавления элемента в конец двусвязного списка?

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

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

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