Защо операцията по добавяне на елемент в началото на свързан списък е по-бърза, отколкото в динамичен масив?

В свързан списък добавянето на елемент в началото е операция с постоянен време 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;
    }
}