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

Amazing thank you so much ~!

Thank you for this great chart!

Thanks! source?

Thank you

Awesome! Great reference, but its missing Stack.

So LinkedList under List Interface uses Linked List data structure. But LinkedList under Queue interface uses Array? How??

@ChiragBagla

ArrayDequeue spelled wrong. Should be ArrayDeque. And Data Structure for ArrayDeque is array.

HashMap should be log(n) if worst case

Thanks!
What about constructors?
They are not always as added.

I think you switched data structures for LinkedList and ArrayDeque

This is beautiful. Good job and thank you.

I think you switched data structures for LinkedList and ArrayDeque

@pszeliga I second you

In Queue section LinkedList isnt an Array and ArrayDequeue based on cycled array

Thank You

In case of O(h / n) may i know the 'h' value and what does it stands for.

LinkedList remove is only O(1) if you use its iterator. standard remove(Object) is O(n)

In case of O(h / n) may i know the 'h' value and what does it stands for.

h stands for the current capacity of the hash collection.

@psayre23 could you explain or anybody why there is no put/add operation for map in table above?

Simply amazing. Thank you.

It really helps me to prepare for my CS exam! Thank you!!

For Queue, the 2nd column head would be "peek" instead of "peak"

Thank you bro

Very useful! Thanks!

Thankyou! Only a small mistake that I think is LinkedList remove is O(N) not O(1) because it first needs to find the node before deleting it.

thanks !!!

Very useful. Thank you!

Great!!! Thanks!

Thanks a lot! Very helpful!

This is great! Thanks
you might need to swap datastructure of ArrayDeque and LinkedList under Deque

Awesome! Great reference, but its missing Stack.

Very helpful indeed.
Please, add the stack as @firstpixel mentioned.
Thanks.

Thank you for this!

Wow! Thank you! That's very helpful!

How O(1) for adding in arraylist?

Thanks, Great Resource! I have to build my Programs in a way that saves time!

Thankyou! Only a small mistake that I think is LinkedList remove is O(N) not O(1) because it first needs to find the node before deleting it.

Correct

To the point. Thanks man!

just curious how about the complexity of ArrayList.addAll(Collection)? is it Constant time?

just curious how about the complexity of ArrayList.addAll(Collection)? is it Constant time?

@Barry36 nope, it's O(M+N) where M = array size (the ArrayList) and N = collection size (the function argument Collection).

FYI, the source code of ArrayList.addAll in JDK 11:

    /**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return {@code true} if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }

1. In the very first line of code, it converts collection to array. If the collections is for example a LinkedList, this means it needs to iterate over all the elements and insert it into a new array, so this is already O(N).
2. In the worst case scenario, the array (of the ArrayList) doesn't have enough capacity to "accommodate" the new elements to be added, so it needs to create a copy of the current elements into a new bigger array (O(M)).
3. Finally, it uses System.arraycopy to copy the array of new elements (of the Collection) into the grown array (of the ArrayList). I didn't see the source code of the System.arraycopy function, but the easiest and most intuitive way of implementing an array copy is iterating over all elements, which makes it O(N) again. But even if the implementation of this had better time complexity, the overall time complexity of the addAll function would not change. Imagine System.arraycopy is O(1), the complexity of the whole function would still be O(M+N). And if the complexity of the System.arraycopy was O(N), overall complexity would still be O(M+N).

good thanks

Hi, can you please add Vector?

How O(1) for adding in arraylist?

Being a list, you always add at the end and having an array as the underlying data structure access is O(1).

If you are asking about having to grow the array and the time in reallocating that memory and copying it, it is done through amortized complexity: each time we add an element that goes beyond the total size of the array, the capacity is doubled. So that way, most of the times you add a new element you just add at the end with O(1) and doing an average, the runtime is constant https://stackoverflow.com/a/45243529/15001063

LinkedList remove is only O(1) if you use its iterator. standard remove(Object) is O(n)

Thankyou! Only a small mistake that I think is LinkedList remove is O(N) not O(1) because it first needs to find the node before deleting it.

Yes.

Check out this link:
https://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures

thanks !!!

best gist ever!