# 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                                                                |
| --------- | --------------------------------------------------------------------------- | --------------------------------------------------------------------------------- | --------------------------------------------------------------------------- | --------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------- |
| `Set`     | [HashSet](https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html) |                                                                                   | [TreeSet](https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html) |                                                                                   | [LinkedHashSet](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html) |
| `List`    |                                                                             | [ArrayList](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html)   |                                                                             | [LinkedList](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html) |                                                                                         |
| `Deque`   |                                                                             | [ArrayDeque](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html) |                                                                             | [LinkedList](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html) |                                                                                         |
| `Map`     | [HashMap](https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html) |                                                                                   | [TreeMap](https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html) |                                                                                   | [LinkedHashMap](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html) |

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F6cdf665dd835c26f441e327a1603373578632357.png?generation=1588144786173030\&alt=media)

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 <a href="#big-o-worst-case-time-complexity-of-data-structures-implemented-in-java" id="big-o-worst-case-time-complexity-of-data-structures-implemented-in-java"></a>

[https://robgrzel.github.io/data structures/complexity/datastructures-time-complexity/](https://robgrzel.github.io/data%20structures/complexity/datastructures-time-complexity/)

Stack Overflow: [What are the time complexities of various data structures?](https://stackoverflow.com/questions/7294634/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](https://www.baeldung.com/java-collections-complexity) 👍

### 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                |