Forked from psayre23/gist:c30a821239f4818b0709
Last active
March 29, 2019 02:43
Revisions
-
shichao-an revised this gist
Jun 18, 2018 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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 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 -
shichao-an revised this gist
Jun 18, 2018 . 1 changed file with 2 additions and 2 deletions.There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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) | 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 -
psayre23 revised this gist
Jan 3, 2015 . 1 changed file with 30 additions and 30 deletions.There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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 | 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 -
psayre23 created this gist
Jan 3, 2015 .There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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