Skip to content

Instantly share code, notes, and snippets.

Revisions

  1. shichao-an revised this gist Jun 18, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.java
    Original file line number Diff line number Diff line change
    @@ -24,7 +24,7 @@
    ------------------------|----------|------|----------|--------|------|---------------
    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) | Linked List
    ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Array
    ArrayDeque | O(1) | O(1) | O(1) | O(n) | O(1) | Array
    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
  2. shichao-an revised this gist Jun 18, 2018. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions gistfile1.java
    Original file line number Diff line number Diff line change
    @@ -23,8 +23,8 @@
    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
    LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Linked List
    ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Array
    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
  3. @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
    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



  4. @psayre23 psayre23 created this gist Jan 3, 2015.
    46 changes: 46 additions & 0 deletions gistfile1.java
    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