Runtime Complexity of Java Collections

gistfile1.java

Below are the Big O performance of common functions of different Java Collections.


List                 | Add  | Remove | Get  | Contains | Next | Data Structure
---------------------|------|--------|------|----------|------|---------------
ArrayList            | O(1) |  O(n)  | O(1) |   O(n)   | O(1) | Array
LinkedList           | O(1) |  O(1)  | O(n) |   O(n)   | O(1) | Linked List
CopyOnWriteArrayList | O(n) |  O(n)  | O(1) |   O(n)   | O(1) | Array



Set                   |    Add   |  Remove  | Contains |   Next   | Size | Data Structure
----------------------|----------|----------|----------|----------|------|-------------------------
HashSet               | O(1)     | O(1)     | O(1)     | O(h/n)   | O(1) | Hash Table
LinkedHashSet         | O(1)     | O(1)     | O(1)     | O(1)     | O(1) | Hash Table + Linked List
EnumSet               | O(1)     | O(1)     | O(1)     | O(1)     | O(1) | Bit Vector
TreeSet               | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree
CopyOnWriteArraySet   | O(n)     | O(n)     | O(n)     | O(1)     | O(1) | Array
ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1)     | O(n) | Skip List



Queue                   |  Offer   | Peak |   Poll   | Remove | Size | Data Structure
------------------------|----------|------|----------|--------|------|---------------
PriorityQueue           | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap
LinkedList              | O(1)     | O(1) | O(1)     |  O(1)  | O(1) | Array
ArrayDequeue            | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List
ConcurrentLinkedQueue   | O(1)     | O(1) | O(1)     |  O(n)  | O(n) | Linked List
ArrayBlockingQueue      | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Array
PriorirityBlockingQueue | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap
SynchronousQueue        | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | None!
DelayQueue              | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap
LinkedBlockingQueue     | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List



Map                   |   Get    | ContainsKey |   Next   | Data Structure
----------------------|----------|-------------|----------|-------------------------
HashMap               | O(1)     |   O(1)      | O(h / n) | Hash Table
LinkedHashMap         | O(1)     |   O(1)      | O(1)     | Hash Table + Linked List
IdentityHashMap       | O(1)     |   O(1)      | O(h / n) | Array
WeakHashMap           | O(1)     |   O(1)      | O(h / n) | Hash Table
EnumMap               | O(1)     |   O(1)      | O(1)     | Array
TreeMap               | O(log n) |   O(log n)  | O(log n) | Red-black tree
ConcurrentHashMap     | O(1)     |   O(1)      | O(h / n) | Hash Tables
ConcurrentSkipListMap | O(log n) |   O(log n)  | O(1)     | Skip List

ArrayDeque's remove - O(n), how is that possible?
If you consider,remove(Object o), then it's OK to be O(n). But for E remove(), it is O(1).
For LinkedList, you wrote O(1), I think you consider E remove() not boolean remove(Object o) or E remove(int index). Because for that two operations, it is O(n). This is also true for PriorityQueue's Remove(). which should be O(log(n))

Sorry I misread it. I thought you meant E remove(int index) in ArrayDeque which I checked and doesn't exist. E remove() removes the first element and being a circular queue it's O(1) of course (same as E removeFirst() and E removeLast()), while remove(Object o), it's O(n) from doing a linear scan O(n) to find the element and then shift all the elements O(n).

I guess @psayre23 chose one of them to keep the formatting of the table?

@psayre23 could you change the file extension to .md and create a good looking table? I feel like a lot of people are using this gist and it would be really good if we got a better looking table than this. I can help you re-write it if you aren't comfortable with markdown too...

Maybe something like this:
https://gist.github.com/cedricvidal/290c161cfe384c4337cd6b76844eeb01

shouldn't the worst time complexity for ArrayList add() operation be O(n) as in the worst case the element might need to be inserted in the middle.

shouldn't the worst time complexity for ArrayList add() operation be O(n) as in the worst case the element might need to be inserted in the middle.

I'm guessing the Add operation of the table refers to add(E e) in the ArrayList doc, which inserts an element at the end. I agree that add(int index, E element) it's an O(n) operation due to possibly needing to shift all elements to the right.

very help full thanks

Thanks for this. One correction ..... For Queue, I am pretty sure it is "peek" and not "peak". Cheers.

PriorityQueue remove() without arguments, it calls poll() which is same as o(log n), and remove(Object) internally calls its private methods which uses comparator so it is also O(log n)