2

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.

Jason Aller
  • 3,541
  • 28
  • 38
  • 38
anthonylouis
  • 45
  • 1
  • 2
  • 6
  • 1
    Did you read the java doc before asking your question ? Doc for Deque states *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.* see https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html – LoneWanderer Nov 27 '18 at 17:41
  • Please follow link https://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures – Madhuri Patel Nov 28 '18 at 12:26
  • Thanks, this link is amazing, i've never found something like this. – anthonylouis Nov 29 '18 at 23:53

1 Answers1

8

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

mettleap
  • 1,390
  • 8
  • 17
  • 2
    @LoneWanderer, I agree ... I added my explanation of what they mean by amortized constant time ... let me know what you think – mettleap Nov 27 '18 at 18:37