Time Complexity: Removal Operations
You'll learn how removing elements from ArrayList and LinkedList differs drastically in efficiency depending on where you remove.
Removing an element from a collection involves two potential costs: finding the element and deleting it. The total time depends on which list implementation you use and where the element lives.
ArrayList: The Shifting Problem
When you remove an element from an ArrayList, Java must shift all subsequent elements one position to the left to fill the gap. If you remove from index 2 in a 1000-element list, you must shift 997 elements.
Think of it like removing a book from the middle of a tightly-packed shelf. Every book to the right must slide left to close the gap.
- Removal from end: O(1) — no shifting needed
- Removal from beginning or middle: O(n) — must shift remaining elements
- Worst case: O(n) for arbitrary removal
LinkedList: Just Update Pointers
LinkedList removal (once you've located the node) is beautifully simple: update two pointers. The previous node's next skips over the removed node, and you're done. No shifting required.
Think of it like unlinking a chain link. You simply reconnect the neighboring links around the one you remove.
- Removal after locating: O(1) — just pointer updates
- However: If you must search by index or value first, that's still O(n)
- Best case: Removing from known head/tail is O(1) total
The Reality Check
Even though LinkedList has O(1) removal mechanics, if you call remove(index) or remove(object), you must first find it—that's O(n). So the total operation is still O(n), just like ArrayList for most removals. The difference matters when you already have a reference to the node.
Key Takeaway: ArrayList removal requires shifting elements (O(n) except at the end); LinkedList removal after locating is just O(1) pointer updates, but finding the element is still O(n).