Sobes.tech
Junior — Middle

Why is adding an element at the beginning of a linked list faster than in a dynamic array?

sobes.tech AI

Answer from AI

In a linked list, adding an element at the beginning is an operation with constant time complexity O(1), because it is enough to create a new node and redirect the reference to it as the new first element. In a dynamic array, however, to add an element at the beginning, all existing elements need to be shifted to the right to make space, which takes O(n) time, where n is the number of elements.

Example in 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;
    }
}
Why is adding an element at the beginning of a linked… - sobes.tech