Array
定义&初始化
两种格式含义相等，只分配了数组引用的存储空间，没有分配数组本身的存储空间。
int[] a1;
int a1[];
初始化：
int[] a1 = {1,2,3,4,5};
// 默认初始化成空值，对于数字就是0，对于布尔型是false
int[] array = new int[10];
对象数组保存的是引用，基本类型数组直接保存数组的值。如下创建了一个引用数组：
Integer[] a = new Integer[20];
直到通过创建新的Integer对象，并把对象赋值给引用，初始化才算结束。
复制
有三种方法，都是浅复制（Shallow Copy）
1.Arrays.copyOf(AnyType[] arr, int len)
2.System.arraycopy
3.arr.clone() 会声明新数组
多维数组
int[][] a = {{1,2,3}, {4,5,6}}
int[][] dir = new int[][] {(0,1),(0,-1),(1,0),(-1,0)};
int[][] dir = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};
求长度
所有数组都有一个固有成员length，可以获取数据元素的数量，但不能修改。
array.length
排序
1.实现Comparable接口，并且使用标准类库的方法Arrays.sort()
2.创建一个实现了Comparator的单独的类
public class Interval {
int start;
int end;
}
Interval[] intervals;
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
查找
如果数组已经排好序了，就可以使用Arrays.binarySearch()执行快速查找。
List
Collection是一个高级接口，包括List, Set, Queue三个子接口。
实现List接口的常用类有ArrayList, LinkedList, Vector, Stack, 其中前三种支持数据的线性存储和定位。
ArrayList
扩容：
Reverse linked list
两种解法：1.Iterative 2.Recursive
LinkedList:
方法：
addFirst(object)
addLast(object)
getFirst()
getLast()
removeFirst()
removeLast()
LinkedList<Integer> q = new LinkedList<Integer>();
q.pollFirst();
q.pollLast();
q.peekFirst();
Thread Safe Lists
Java提供了两种方便的机制：
1.Collections.sychronizedList
2.Vector
Stack:
实现
Java中的栈是线程安全的数据结构
构造
Deque<Integer> stack = new ArrayDeque<Integer>();
方法push, pop
相关题目
Min Stack
程序里检测括号是否对称
Queue:
Java中Queue接口主要方法是poll()和offer()
Queue的实现方法：
1.用LinkedList，维护head和rear
2.用Array，维护头尾两个index，头尾相碰时进行resize
3.用Stack，相关题目：Implement queue using stacks
注意
1.Queue不是线程安全的，Java中线程安全的Queue是Blocking Queue
Java中的阻塞队列
2.Deque接口是Stack和Queue的结合，可以通过它在线性结构头尾两段自由地存取元素。ArrayDeque可以自动扩容，但不是线程安全的，实现原理就是循环数组，因而比Stack和LinkedList快。
ArrayDeque接口：
addFirst(object)
addLast(object)
getFirst()
getLast()
removeFirst()
removeLast()
构造
Deque<Integer> queue = new ArrayDeque<Integer>();
queue.add, queue.poll
queue.addLast()
queue.pollFirst()
Queue的应用
BFS里用到queue，用queue做逐层记录。
Heap：
Min heap:最大的k个数
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> (a.val > b.val ? 1 : -1)); 小根堆？
final PriorityQueue<Integer> pq = new PriorityQueue<>();//minHeap
final PriorityQueue<Integer> pq = new PriorityQueue<>(1000, Collections.reverseOrder());//maxHeap
pq.add(), pq.poll(), pq.peek()
ArrayList:
Object[] = list.toArray()
HashMap:
map.getOrDefault(n,0)
map.containsKey()
Tree
BitSet:
bitset.set()
bitset.get()
bitset.nextClearBit()
bitset.clear()
String:
char charAt(int index);
char[] toCharArray();
String.substring(int beginIndex, int endIndex);
StringBuilder vs StringBuffer
问题：HashTable的实现
线程安全的List
