Why ArrayList Middle Insert Is O(n)

Adding to the middle of an ArrayList is O(n) because of element shifting. An ArrayList stores everything contiguously in an array, so when you insert at index i, every element from i to the end has to move one position to the right to make room. In the worst case — inserting at the front — that's n moves, so it's linear. Removing from the middle is the same idea in reverse: the elements after the gap shift left to close it. Now, appending at the end is different. Most of the time it's O(1), because you just place the element in the next free slot. The exception is when the backing array is full. Then ArrayList creates a new array about fifty percent larger and copies everything across, and that particular add is O(n). But because these resizes happen less and less often as the list grows, the average cost of an append is still O(1) — we call that amortized constant time. One nice detail to mention is that both the shifting and the copying are done with System.arraycopy, which is a fast native bulk memory move, so even though the Big-O is linear the constant factor is small. Two practical tips: if you know roughly how many elements you'll add, pass an initial capacity to the constructor to avoid repeated resizes; and if you need cheap insertion at the front, don't loop add at index zero on an ArrayList because that's quadratic — use an ArrayDeque, which is O(1) at both ends. And remember, switching to LinkedList doesn't fix middle insertion, because you still have to walk to the index first.