1, LinkedList
composed of one and one Node: [data][next].
[head] -> [data][next] -> [data][next] -> [data][next] -> [null].
Empty linkedList: head == null.
V.S. Array DS: fast at insert/delete.
2, hashtable
“数组可以通过下标直接定位到相应的空间”，对就是这句，哈希表的做法其实很简单，就是把Key通过一个固定的算法函数，既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
Hash tables are O(1) average and amortized case complexity, however is suffers from O(n) worst case time complexity.
Hash tables suffer from O(n) worst time complexity due to two reasons:
- If too many elements were hashed into the same key: looking inside this key may take
O(n)time. - Once a hash table has passed its load balance - it has to rehash [create a new bigger table, and re-insert each element to the table].
HashMap<T>也是buckets的概念，但是如果你只override了T class的hashcode()方法返回constant，那么当你往这个HashMap里存放多个object的时候，它们都被hash到了同一个bucket，但它们还是会被当成不同的value来处理。所以只override hashcode()是不够的。
Collision resolution
大多数的hashtable implementations都有collision resolution strategy，所有的方法都会需要将keys（或指向key的指针）随同associated values也存到table中。
Separate chaining:
这种方法中each bucket has some sort of list of entries with the same index. 用Linked lists的Chained hash table很流行，有时会选择用ordered linked list。
3, Binary tree
Binary tree: at most 2 child nodes.
Full Binary tree: depth k and have 2^k -1 nodes.
Binary search tree: left child node< current node< right child node
Define BinaryNode:
class BinaryNode {
BinaryNode left;
BinaryNode right;
int element;
public BinaryNode(int element) {
this.element = element;
left = right = null;
}
}
Function to see if a tree is a BST:
public boolean isBST() {
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBST2(BinaryNode currRoot, int low, int high) { //注意最低限和最高限，并且不断update它
if(currRoot.left != null) {
if(currRoot.left.element < low || currRoot.left.element > currRoot.element || !isBST2(currRoot.left, low, currRoot.element))
return false;
}
if(currRoot.right != null) {
if(currRoot.right.element > high || currRoot.right.element < currRoot.element || !isBST2(currRoot.right, currRoot.element, high))
return false;
}
return true;
}
Breadth-First-Search:[Queue], 这个算法就是要用Queue来实现， Java只有Queue interface, extends Collection
public void bfs() {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root== null) return;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.remove(); //LinkedList.remove() will remove the head of the linked list
System.out.print(node.val + " ");
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}
Depth-First-Search:[Stack] Java有Stack class, implements List interface. 方法peek()返回top，方法pop()返回top并移除。
4, AVL tree
is a self balancing Binary Search Tree, In an AVL tree, the height of two sub-trees of ANY node can not differ more than 1. If any time the height differs more than 1, rebalancing is done to restore the property.
Rebalancing: LL, RR, LR, RL.