Course contentsShow
← Java
Lesson 1039 of 2,87024. List ImplementationsFree lesson

Time Complexity: Insertion at End

ArrayList amortized O(1) add at end; LinkedList O(1) at tail with reference maintained.

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:

  1. Creates a new node
  2. Updates the old tail's next pointer
  3. Updates the tail reference

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.