- 1

Thanks!

*n*) 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.

Campbell Ritchie wrote:In an ArrayList, however, it would be O(log

n) 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.

Ernest Friedman-Hill wrote:

Removing from a linked list does, indeed, always take constant time.

Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.

Cheryl Scodario wrote:

Ernest Friedman-Hill wrote:

Removing from a linked list does, indeed, always take constant time.

Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.

*Finding*an object takes linear time; subsequently

*removing*it takes constant time. For an array,

*finding*takes linear time for unsorted, and logarithmic time for a sorted list; and

*removing*takes linear time.

Removing does not always imply finding. For example, consider removing the first element of a list. For a linked list, it's done in constant time, and for an array or ArrayList, it takes linear time.

Ernest Friedman-Hill wrote:

Cheryl Scodario wrote:

Ernest Friedman-Hill wrote:

Removing from a linked list does, indeed, always take constant time.

Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.

Findingan object takes linear time; subsequentlyremovingit takes constant time. For an array,findingtakes linear time for unsorted, and logarithmic time for a sorted list; andremovingtakes linear time.

Removing does not always imply finding. For example, consider removing the first element of a list. For a linked list, it's done in constant time, and for an array or ArrayList, it takes linear time.

I see...How about insert in a sorted list? I always think of remove and insert very similar. But is insert implying find for sure? Because you need to find the right position to insert it. Then it would be N, linear time?

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

fred rosenberger wrote:Not if you are inserting in the first position.

I am not talking about any special(best) case. So let's just say sorted list: insert and find (average case).

It is sorta covered in the JavaRanch Style Guide. |