Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Runtime Complexity of Java Collections
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
@shrishar

This comment has been minimized.

Copy link

@shrishar shrishar commented Aug 30, 2017

Amazing thank you so much ~!

@bitnahian

This comment has been minimized.

Copy link

@bitnahian bitnahian commented Sep 21, 2017

Thank you for this great chart!

@rafareyes7

This comment has been minimized.

Copy link

@rafareyes7 rafareyes7 commented Sep 27, 2017

Thanks! source?

@SurendraVidiyala

This comment has been minimized.

Copy link

@SurendraVidiyala SurendraVidiyala commented Oct 5, 2017

Thank you

@firstpixel

This comment has been minimized.

Copy link

@firstpixel firstpixel commented Nov 24, 2017

Awesome! Great reference, but its missing Stack.

@pendawleabhay

This comment has been minimized.

Copy link

@pendawleabhay pendawleabhay commented Nov 29, 2017

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

@ayush--s

This comment has been minimized.

Copy link

@ayush--s ayush--s commented Dec 31, 2017

@vlytsus

This comment has been minimized.

Copy link

@vlytsus vlytsus commented Jan 30, 2018

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

@ArseniyChern

This comment has been minimized.

Copy link

@ArseniyChern ArseniyChern commented Feb 3, 2018

HashMap should be log(n) if worst case

@baruchiro

This comment has been minimized.

Copy link

@baruchiro baruchiro commented Mar 27, 2018

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

@pszeliga

This comment has been minimized.

Copy link

@pszeliga pszeliga commented May 16, 2018

I think you switched data structures for LinkedList and ArrayDeque

@matthewmarkose

This comment has been minimized.

Copy link

@matthewmarkose matthewmarkose commented May 29, 2018

This is beautiful. Good job and thank you.

@abcoep

This comment has been minimized.

Copy link

@abcoep abcoep commented Jun 3, 2018

I think you switched data structures for LinkedList and ArrayDeque

@pszeliga I second you

@slavadolg

This comment has been minimized.

Copy link

@slavadolg slavadolg commented Jun 25, 2018

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

@prajeethrudra

This comment has been minimized.

Copy link

@prajeethrudra prajeethrudra commented Aug 1, 2018

Thank You

@Bhagyasree1234

This comment has been minimized.

Copy link

@Bhagyasree1234 Bhagyasree1234 commented Aug 19, 2018

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

@lare96

This comment has been minimized.

Copy link

@lare96 lare96 commented Oct 16, 2018

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

@digi9ten

This comment has been minimized.

Copy link

@digi9ten digi9ten commented Oct 25, 2018

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.

@dmitry-izmerov

This comment has been minimized.

Copy link

@dmitry-izmerov dmitry-izmerov commented Dec 3, 2018

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

@enkeebbx

This comment has been minimized.

Copy link

@enkeebbx enkeebbx commented Mar 11, 2019

Simply amazing. Thank you.

@ZhijianD

This comment has been minimized.

Copy link

@ZhijianD ZhijianD commented Apr 5, 2019

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

@chinmay2312

This comment has been minimized.

Copy link

@chinmay2312 chinmay2312 commented Apr 7, 2019

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

@dongw00

This comment has been minimized.

Copy link

@dongw00 dongw00 commented Apr 14, 2019

Thank you bro

@cmulation

This comment has been minimized.

Copy link

@cmulation cmulation commented Jun 18, 2019

Very useful! Thanks!

@agrawalankit006

This comment has been minimized.

Copy link

@agrawalankit006 agrawalankit006 commented Jul 11, 2019

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.

@HUAZHEYINy

This comment has been minimized.

Copy link

@HUAZHEYINy HUAZHEYINy commented Aug 5, 2019

thanks !!!

@LisaFan18

This comment has been minimized.

Copy link

@LisaFan18 LisaFan18 commented Sep 14, 2019

Very useful. Thank you!

@VasilSokolov

This comment has been minimized.

Copy link

@VasilSokolov VasilSokolov commented Nov 1, 2019

Great!!! Thanks!

@MariaForester

This comment has been minimized.

Copy link

@MariaForester MariaForester commented Nov 17, 2019

Thanks a lot! Very helpful!

@zeiadzaf

This comment has been minimized.

Copy link

@zeiadzaf zeiadzaf commented Dec 21, 2019

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

@lucallero

This comment has been minimized.

Copy link

@lucallero lucallero commented Feb 23, 2020

Awesome! Great reference, but its missing Stack.

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

@o-x-y-g-e-n

This comment has been minimized.

Copy link

@o-x-y-g-e-n o-x-y-g-e-n commented Mar 9, 2020

Thank you for this!

@Hydor

This comment has been minimized.

Copy link

@Hydor Hydor commented Apr 1, 2020

Wow! Thank you! That's very helpful!

@priyodas12

This comment has been minimized.

Copy link

@priyodas12 priyodas12 commented Apr 26, 2020

How O(1) for adding in arraylist?

@ssavva05

This comment has been minimized.

Copy link

@ssavva05 ssavva05 commented May 24, 2020

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

@shyamzzp

This comment has been minimized.

Copy link

@shyamzzp shyamzzp commented Aug 10, 2020

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

@ashtnemi448

This comment has been minimized.

Copy link

@ashtnemi448 ashtnemi448 commented Sep 23, 2020

To the point. Thanks man!

@Barry36

This comment has been minimized.

Copy link

@Barry36 Barry36 commented Nov 2, 2020

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

@mcanalesmayo

This comment has been minimized.

Copy link

@mcanalesmayo mcanalesmayo commented Nov 11, 2020

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).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment