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
Set HashSet TreeSet LinkedHashSet
List ArrayList LinkedList
Deque ArrayDeque LinkedList
Map HashMap TreeMap LinkedHashMap

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

results matching ""

    No results matching ""