CODEWITHSUNDEEP
javadata-structuresarraylistcomplexity-theorybig-o
voidMainReturn
voidMainReturn

Reputation: 3507

what is the running time for insertion of an element at some index of arrayList?

I was wondering what is the running time for add(index,E) method of java ArrayList. According to the javadoc the running time for add operation is amortized O(1). But in the description of add(index,E) it says that.

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

So it looks like O(N). I was wondering what do we have to trade for, if running time for this operation was to make O(1). Is there any amortization work that can be done to make this operation O(1) and sacrifice running time for some other operation ?

I read that java ArrayList is backed by arrays, would changing the data structure help?

Upvotes: 5

Views: 3411

Answers (2)

AllTooSir
AllTooSir

Reputation: 49372

ArrayList has O(n) time complexity for arbitrary indices of add/remove, but O(1) for the operation at the end of the list. Closer to O(1) lookup implies may be something like a Hash Table backed data structure with index as key and element as value. Insertion again will take O(n) time because it triggers a resize.

Upvotes: 3

Rob
Rob

Reputation: 6497

A naive implementation of an array-backed list would copy each item to be moved on an insert as a separate operation. Fortunately, the bytes to be moved are all contiguous in memory and every operating system provides support for efficiently copying large chunks of memory in a single, fast operation.

So inserting into the middle of an array isn't as bad as you might think. Of course, changing the data structure to a linked list might prove to be faster if your application has the right kind of access pattern.

Upvotes: 2

Related Questions