Skip to content

Instantly share code, notes, and snippets.

@shockyng

shockyng/gist:a2f6fe0431329889e115560c519a4ec6

Forked from psayre23/gist:c30a821239f4818b0709
Created October 22, 2022 17:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shockyng/a2f6fe0431329889e115560c519a4ec6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shockyng/a2f6fe0431329889e115560c519a4ec6 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @psayre23 psayre23 revised this gist Jan 3, 2015. 1 changed file with 30 additions and 30 deletions.
    60 changes: 30 additions & 30 deletions gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,36 +1,36 @@
    Below are the Big O performance of common functions of different Java Collections.


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



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



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



  2. @psayre23 psayre23 created this gist Jan 3, 2015.
    46 changes: 46 additions & 0 deletions gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    Below are the Big O performance of common functions of different Java Collections.


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



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



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