Data Structure & Design
HashMap
https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html
HashMap 的两种遍历方式 第一种
效率高,以后一定要使用此种方式!
第二种
效率低,以后尽量少使用!
Map Traverse:
The Collection view methods allow a Map to be viewed as a Collection in these three ways:
keySet — the Set of keys contained in the Map.
values — The Collection of values contained in the Map. This Collection is not a Set, because multiple keys can map to the same value.
entrySet — the Set of key-value pairs contained in the Map. The Map interface provides a small nested interface called Map.Entry, the type of the elements in this Set.
Differences Between HashMap Vs HashSet In Java
https://javaconceptoftheday.com/differences-between-hashmap-vs-hashset-in-java/
Union Find (Disjoint Set)
并查集: 一种用来解决集合查询合并的数据结构 支持O(1) find / O(1) union
并查集可以干什么?
判断在不在同一个集合中。
find 操作
关于集合合并
union 操作
并查集的操作
查询 Find (递归? 非递归?)
模板代码
合并 Union
老大哥之间合并 跟小弟没关系
并查集完整模板
Trie
Linked List vs ArrayList
LinkedList
and ArrayList
are two different implementations of the List interface. LinkedList
implements it with a doubly-linked list. ArrayList
implements it with a dynamically re-sizing array.
LinkedList<E>
allows for constant-time insertions or removals using iterators, but only sequential access of elements.
ArrayList<E>
, on the other hand, allow fast random read access, so you can grab any element in constant time.
ArrayList | LinkedList |
1) ArrayList internally uses a dynamic array to store the elements. | LinkedList internally uses a doubly linked list to store the elements. |
2) Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory. | Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory. |
3) An ArrayList class can act as a list only because it implements List only. | LinkedList class can act as a list and queue both because it implements List and Deque interfaces. |
4) ArrayList is better for storing and accessing data. | LinkedList is better for manipulating data. |
Heap
Heap
A min-heap is a binary tree such that
the data contained in each node is less than (or equal to) the data in that node’s children.
the binary tree is complete
A max-heap is a binary tree such that
the data contained in each node is greater than (or equal to) the data in that node’s children.
the binary tree is complete
Sift Up
Sift Down
Resources
Stack
Queue
ArrayDeque / Deque
ArrayDeque
It’s not thread-safe
Null elements are not accepted
Works significantly faster than the synchronized Stack
Is a faster queue than LinkedList due to the better locality of reference
Most operations have amortized constant time complexity
An Iterator returned by an ArrayDeque is fail-fast
ArrayDeque automatically doubles the size of an array when head and tail pointer meets each other while adding an element
An ArrayDeque implementation can be used as a Stack (Last-In-First-Out) or a Queue(First-In-First-Out).
In Java Docs for ArrayDeque:
This class is likely to be faster than
Stack
when used as a stack, and faster thanLinkedList
when used as a queue.
Deque Interface:
https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html
Arrays
java.util.Arrays
https://www.geeksforgeeks.org/array-class-in-java/
Methods
1.static List asList(T… a)
: This method returns a fixed-size list backed by the specified array.
static int binarySearch(elementToBeSearched)
: These methods searches for the specified element in the array with the help of Binary Search algorithm.
copyOf(originalArray, newLength)
: This method copies the specified array, truncating or padding with the default value (if necessary) so the copy has the specified length.
fill(originalArray, fillValue)
: This method assigns this fillValue to each index of this array.
TreeSet / TreeMap
TreeMap
https://www.baeldung.com/java-treemap
Default Sorting in TreeMap
Custom Sorting in TreeMap
TreeSet
https://www.baeldung.com/java-tree-set
In this implementation, objects are sorted and stored in ascending order according to their natural order. The _TreeSet _uses a self-balancing binary search tree, more specifically a _Red-Black _tree.
Operations like add
, remove
and contains
(search) take O(log n)
time while operations like printing n elements in sorted order require O(n)
time.
Comparator
Although TreeSet isn’t thread-safe, it can be synchronized externally using the Collections.synchronizedSet()
wrapper:
TreeSet add()
TreeSet contains()
TreeSet remove()
TreeSet & TreeMap
The TreeSet internally depends on a backing NavigableMap which gets initialized with an instance of TreeMap when an instance of the TreeSet is created:
Last updated