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;
}
}