Data Structures in Java
Data Structures in Java
Java Collections Framework Overview
https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html
Interface | Hash Table | Resizable Array | Balanced Tree | Linked List | Hash Table + Linked List |
| |||||
| |||||
| |||||
|
The Collection Interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html
Map Interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html
Big-O time complexity of Data Structures implemented in Java
https://robgrzel.github.io/data structures/complexity/datastructures-time-complexity/
Stack Overflow: What are the time complexities of various data structures? 👍
https://robgrzel.github.io/assets/images/datastructures-complexity-java.pdf
http://files.zeroturnaround.com/pdf/zt_java_collections_cheat_sheet.pdf 👍
Baeldung: Time Complexity of Java Collections 👍
Below are the Big O performance of common functions of different Java Collections.
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
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
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
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 |
Last updated
