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
Was this helpful?