Time Complexity: Insertion at End
You'll learn why adding elements to the end behaves differently in ArrayList vs LinkedList.
Core Idea
When you append an element to the end of a list, the time complexity depends entirely on the underlying data structure. For ArrayList, it's amortized O(1)—usually instant, occasionally costly. For LinkedList, it's always O(1) when a tail reference is maintained.
ArrayList: Amortized O(1)
When you call add(element) on an ArrayList, it places the new element at the next available slot in the backing array. Most of the time, this is a single assignment operation—genuinely O(1).
However, when the array is full, the operation triggers a resize: allocating a larger array (1.5x capacity) and copying all existing elements. That single add becomes O(n).
Over many operations, the expensive resizes are rare enough that the average cost per insertion remains constant—this is called amortized O(1). Think of it like a subscription service: you pay a big fee occasionally (annual renewal), but the per-day cost averages out to pennies.
LinkedList: True O(1)
A LinkedList maintains both head and tail references. When you add to the end, it simply:
- Creates a new node
- Updates the old tail's
nextpointer - Updates the
tailreference
No iteration. No array copying. Just pointer manipulation—always O(1), no amortization needed. It's like adding a caboose to a train: you only touch the current last car and the new one.
When It Matters
If you're building a list with millions of elements and can't afford occasional O(n) pauses, LinkedList's predictable behavior wins. If you value simplicity and faster iteration later, ArrayList's amortized performance is excellent.
Key Takeaway:
ArrayList offers amortized O(1) insertion at the end (occasional resizes), while LinkedList provides true O(1) insertion when a tail reference is maintained.