Time Complexity: Insertion at Beginning
What you'll learn: You'll discover why inserting at the head of a LinkedList is instant while ArrayList struggles with the same operation.
When you insert an element at the beginning of a collection, the two implementations behave dramatically differently due to their internal structures.
LinkedList: O(1) — Constant Time
LinkedList simply creates a new node and updates its head reference to point to this new node, linking it to the former first element. No matter if the list contains 10 or 10,000 elements, this operation takes the same fixed number of steps: create node, update pointer, done.
Analogy: Imagine a chain of paper clips. Adding a new clip to the front just means attaching it to what was previously first—you never touch the rest of the chain.
ArrayList: O(n) — Linear Time
ArrayList stores elements in a contiguous array. To insert at position 0, it must shift every single existing element one position to the right to make room. If you have 1,000 elements, that's 1,000 copy operations via System.arraycopy.
Analogy: Think of a row of parked cars. To add a car at the front, every single car must back up one space. The more cars, the longer it takes.
The Performance Gap
For addFirst() or add(0, element):
- LinkedList: Always fast, regardless of size
- ArrayList: Gets slower as the list grows
If your application frequently inserts at the beginning (like implementing a stack or certain queue patterns), LinkedList dramatically outperforms ArrayList.
Key Takeaway: LinkedList inserts at the head in O(1) constant time by updating pointers, while ArrayList requires O(n) time to shift all elements, making LinkedList superior for frequent front insertions.