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

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

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

Пример добавления в начало односвязного списка на Java:

class Node {
    int value;
    Node next;
    Node(int val) { value = val; }
}

class LinkedList {
    Node head;

    void addFirst(int val) {
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
    }
}

Здесь операция addFirst — O(1).