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

Пример на Java:

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

class LinkedList {
    Node head;
    void addFirst(int value) {
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode;
    }
}

Почему операция добавления элемента в начале связанного списка выполняется быстрее, чем в динамическом массиве?