1

For Java ArrayList, is it accurate to say add and remove by index run in amortized constant time, meaning on average it is constant time (in rare cases linear time by setting up the memory so future operations are faster)?

Improve this question
3
  • Did you see stackoverflow.com/questions/7910283/… ? Commented Oct 2, 2016 at 17:56
  • Yes but that didn't seem index based. I'm talking only indexes. Commented Oct 2, 2016 at 17:58
  • General performance of ArrayList and LinkedList methods are answered in this answer. It also contains adding an element at an index, or removing an element at an index. Commented Oct 2, 2016 at 18:04

2 Answers 2

Reset to default
0

No, this would not be accurate to say that insertion and removal of elements from ArrayList by index is amortized constant time, because there is no amortization going on for copying of data.

Only list expansions and their associated copying are amortized, because they happen infrequently*. However, this requires insertions at the end of the list.

When you insert at the beginning of the list, expansions are still amortized, but copies required to move elements by 1 position happen on every call, and are not amortized.

* In order to be able to amortize the cost of an operation you need a mix of "cheap" and "expensive" operations. In this situation you can split the total cost among all operations, getting you a lower result.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

So if my list is 100,000 long and I insert in the middle, it would need to move over everything after 500,000 first? I.e. linear time?
@SeanHill Correct. Every time you insert in the middle you move the "tail" by one to make space for the new element, and then you set the element to the intended value. Inserting k elements in the middle of an n-element list is O(k*n/2).
But then additional time is needed if there are too many inserts so it copies the entire array to a new spot in memory with 2(n+k) contiguous free/null spaces?
@SeanHill Yes, but that additional time is amortized, because doubling of the array does not happen on every call. (to be exact, it's not doubling, because Java is using a factor of 1.5).
But we can init lists to whatever size we want, how much space does it allocate up front / when does it trigger the multiply / why 1.5?
|
0

For add(Object) yes, but for remove(int index) it's constant time only if you're removing the last element, since otherwise the elements are shifted to remove any nulls from the middle of the array.

Index based add (and remove from not last position) aren't amortized constant time, they're linear time.

Improve this answer

15 Comments

I'm talking indexes only, as in add this object in position 5
@SeanHill See edit.
So then wait how is add object not linear? Or is this more like an append to end which is constant time unless the list capacity is doubled?
It's not "like", add() is append to end. It's constant unless the array needs to be resized.
I'd have to check again but I thought there was an add (object, index) method where add is used as insert
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.