I've read in some places that LinkedList in Java have O(1) time complexity to add and remove elements but O(n) to get elements. And ArrayList have O(1) to get elements and O(n) to add and remove.
I have a program which has to do many operations involving insertion and recovery elements from a list. So, I would like to know if ArrayDeque time to access a element is similar to ArrayList.
From the javadoc, it is written,
Most ArrayDeque operations run in amortized constant time. Exceptions include remove,
removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk
operations, all of which run in linear time.
So, removing an element is linear time operation, getting it should be O(1).
EDIT:
Amortized constant time operation means most of the time the operation cost will O(1), except possibly in some cases, for eg. when the ArrayDeque needs to be resized. The javadoc for ArrayDeque also says,
Array deques have no capacity restrictions; they grow as necessary to support usage
So, whenever new elements are added to the end or start of the ArrayDeque, its size changes -> consequently if the total number of elements violate the capacity property of the ArrayDeque, it needs to be resized, which might be higher than O(1). But if you do a lot of such operations and average out the time-complexity, it will be very close to O(1).
