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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/problem-solving-summary/java-interview-tips/data-structures-in-java.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.