Skip to content

Instantly share code, notes, and snippets.

@psayre23
Last active March 14, 2024 13:25
Show Gist options
  • Save psayre23/c30a821239f4818b0709 to your computer and use it in GitHub Desktop.
Save psayre23/c30a821239f4818b0709 to your computer and use it in GitHub Desktop.
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
@o-x-y-g-e-n
Copy link

Thank you for this!

@Hydor
Copy link

Hydor commented Apr 1, 2020

Wow! Thank you! That's very helpful!

@priyodas12
Copy link

priyodas12 commented Apr 26, 2020

How O(1) for adding in arraylist?

@ssavva05
Copy link

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

@shyamzzp
Copy link

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
Copy link

To the point. Thanks man!

@Barry36
Copy link

Barry36 commented Nov 2, 2020

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

@mcanalesmayo
Copy link

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

@kumaresan-perumal
Copy link

good thanks

@kumaresan-perumal
Copy link

Hi, can you please add Vector?

@davitescobedo
Copy link

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

@ahmedghallab
Copy link

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

@zhengyin
Copy link

thanks !!!

@oziris78
Copy link

best gist ever!

@nowshad-hasan
Copy link

nowshad-hasan commented Mar 28, 2022

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

@eldavimost
Copy link

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

It comes from shifting all elements to fill in the new empty space left after the element you remove.

@nowshad-hasan
Copy link

nowshad-hasan commented Mar 29, 2022

@eldavimost
From Javadoc,

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, if you consider amortized, then you can say O(n), but most of the time, it's O(1)

@eldavimost
Copy link

eldavimost commented Mar 29, 2022

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?

@oziris78
Copy link

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

@oziris78
Copy link

@upanshu21
Copy link

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.

@davitescobedo
Copy link

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.

@YemaneHadis
Copy link

very help full thanks

@NawaMan
Copy link

NawaMan commented Feb 13, 2023

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

@venukbh
Copy link

venukbh commented Mar 24, 2023

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment