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)?

Sean Hill
  • 1,297
  • 1
  • 13
  • 21
  • Did you see https://stackoverflow.com/questions/7910283/java-arraylist-add-and-remove-performance-implementation?rq=1 ? –  Oct 02 '16 at 17:56
  • Yes but that didn't seem index based. I'm talking only indexes. – Sean Hill Oct 02 '16 at 17:58
  • General performance of ArrayList and LinkedList methods are answered in [this answer](http://stackoverflow.com/a/322742/1743880). It also contains adding an element at an index, or removing an element at an index. – Tunaki Oct 02 '16 at 18:04

2 Answers2

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.

Kayaman
  • 72,141
  • 5
  • 83
  • 121
  • I'm talking indexes only, as in add this object in position 5 – Sean Hill Oct 02 '16 at 17:59
  • @SeanHill See edit. – Kayaman Oct 02 '16 at 18:02
  • 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? – Sean Hill Oct 02 '16 at 18:04
  • It's not "like", `add()` is append to end. It's constant unless the array needs to be resized. – Kayaman Oct 02 '16 at 18:06
  • I'd have to check again but I thought there was an add (object, index) method where add is used as insert – Sean Hill Oct 02 '16 at 18:10
  • @SeanHill Which is what I'm referring to with my "Index based `add`" claim at the end of my answer. We have `add(Object)` which is amortized constant time and `add(Object, int)` which is linear. Remove is linear unless removing from the end. – Kayaman Oct 02 '16 at 18:12
  • (Agreed, I was just contesting that add always means at the end) – Sean Hill Oct 02 '16 at 18:13
  • The indexed add is not very often used. – Kayaman Oct 02 '16 at 18:16
  • Why is that? Do people insert using another aporoach? – Sean Hill Oct 02 '16 at 18:16
  • People don't insert into the middle of lists. – Kayaman Oct 02 '16 at 18:23
  • What do they use then if they are displaying a list in an app where people can move items around, add, or delete them? – Sean Hill Oct 02 '16 at 18:36
  • I'm talking about *common* use cases. The kind of app you described isn't exactly in high demand business-wise. – Kayaman Oct 02 '16 at 18:41
  • Scheduling apps? Routine apps? Planning apps? Travel apps? – Sean Hill Oct 02 '16 at 19:05
  • All possible (and most likely written) without calling the index based add. A developer is a lot more likely to call `add(Object)` than `add(Object, int)`. Sorting could be a use case, but since `List.sort()` has direct access to the internal data, it's not very valid. All in all it's just not a very important method. – Kayaman Oct 02 '16 at 19:21
  • But certainly they use delete, and they can rearrange arbitrarily – Sean Hill Oct 02 '16 at 19:31
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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 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? – Sean Hill Oct 02 '16 at 18:01
  • @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). – Sergey Kalinichenko Oct 02 '16 at 18:04
  • 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? – Sean Hill Oct 02 '16 at 18:07
  • @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). – Sergey Kalinichenko Oct 02 '16 at 18:13
  • 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? – Sean Hill Oct 02 '16 at 18:15
  • @SeanHill The amount of space you allocate upfront makes no difference for inserting in the middle, because it saves you the expansion, which is O(1) amortized anyway. Copying of the tail is what's not amortized, and it is not going away, no matter how much space you allocate upfront. – Sergey Kalinichenko Oct 02 '16 at 18:32