Campbell Ritchie wrote:In an ArrayList, however, it would be O(logn) if it is already sorted and O(n) if not sorted. If you already know the index, it would be constant time. To obtain the logarithmic time you would need a binary search to find the element to remove.
Actually, no. Removing an element from an ordered array or ArrayList takes
linear time, because after you remove the element, you then have to move an average of N/2 elements down to fill the "hole". If order doesn't matter, then you can just move the last element, and that does take constant time; of course, then you might as well have been using a Set rather than a List in the first place.
Removing from a linked list does, indeed, always take constant time.