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

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

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

Пример с указателем на хвост:

class LinkedList {
    Node head;
    Node tail;

    void addLast(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}