本文采用Java語言來進行描述，幫大家好好梳理一下數據結構與算法，在工作和麵試中用的上。亦即總結常見的的數據結構，以及在Java中相應的實現方法，務求理論與實踐一步總結到位。
好好梳理一下數據結構與算法，畢竟這些基礎知識是很重要的嘛
首先給出Java集合框架的基本接口/類層次結構：
java.util.Collection [I]
+--java.util.List [I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C] //線程安全
+--java.util.Stack [C] //線程安全
+--java.util.Set [I]
+--java.util.HashSet [C]
+--java.util.SortedSet [I]
+--java.util.TreeSet [C]
+--Java.util.Queue[I]
+--java.util.Deque[I]
+--java.util.PriorityQueue[C]
java.util.Map [I]
+--java.util.SortedMap [I]
+--java.util.TreeMap [C]
+--java.util.Hashtable [C] //線程安全
+--java.util.HashMap [C]
+--java.util.LinkedHashMap [C]
+--java.util.WeakHashMap [C]
[I]：接口
[C]：類
常用數據結構
數組
數組是相同數據類型的元素按一定順序排列的集合，是一塊連續的內存空間。數組的優點是：get和set操作時間上都是O(1)的；缺點是：add和remove操作時間上都是O(N)的。
Java中，Array就是數組，此外，ArrayList使用了數組Array作為其實現基礎,它和一般的Array相比，最大的好處是，我們在添加元素時不必考慮越界，元素超出數組容量時，它會自動擴張保證容量。
Vector和ArrayList相比，主要差別就在於多了一個線程安全性，但是效率比較低下。如今java.util.concurrent包提供了許多線程安全的集合類（比如 LinkedBlockingQueue），所以不必再使用Vector了。
int[] ints = new int[10];
ints[0] = 5;//set
int a = ints[2];//get
int len = ints.length;//數組長度
鏈表
鏈表是一種非連續、非順序的結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的，鏈表由一系列結點組成。鏈表的優點是：add和remove操作時間上都是O(1)的；缺點是：get和set操作時間上都是O(N)的，而且需要額外的空間存儲指向其他數據地址的項。
查找操作對於未排序的數組和鏈表時間上都是O(N)。
Java中，LinkedList 使用鏈表作為其基礎實現。
LinkedList<string> linkedList = new LinkedList<>();
linkedList.add("addd");//add
linkedList.set(0,"s");//set，必須先保證 linkedList中已經有第0個元素
String s = linkedList.get(0);//get
linkedList.contains("s");//查找
linkedList.remove("s");//刪除
/<string>
//以上方法也適用於ArrayList
隊列
隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端進行刪除操作，而在表的後端進行插入操作，亦即所謂的先進先出（FIFO）。
Java中，LinkedList實現了Deque，可以做為雙向隊列（自然也可以用作單向隊列）。另外PriorityQueue實現了帶優先級的隊列，亦即隊列的每一個元素都有優先級，且元素按照優先級排序。
Deque<integer> integerDeque = new LinkedList<>();
// 尾部入隊，區別在於如果失敗了
// add方法會拋出一個IllegalStateException異常，而offer方法返回false
integerDeque.offer(122);
integerDeque.add(122);
// 頭部出隊,區別在於如果失敗了
// remove方法拋出一個NoSuchElementException異常，而poll方法返回false
int head = integerDeque.poll();//返回第一個元素，並在隊列中刪除
head = integerDeque.remove();//返回第一個元素，並在隊列中刪除
// 頭部出隊，區別在於如果失敗了
// element方法拋出一個NoSuchElementException異常，而peek方法返回null。
head = integerDeque.peek();//返回第一個元素，不刪除
head = integerDeque.element();//返回第一個元素，不刪除
/<integer>
棧
棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。它體現了後進先出（LIFO）
的特點。
Java中，Stack實現了這種特性，但是Stack也繼承了Vector，所以具有線程安全線和效率低下兩個特性，最新的JDK8中，推薦用Deque來實現棧，比如：
Deque<integer> stack = new ArrayDeque<integer>();
stack.push(12);//尾部入棧
stack.push(16);//尾部入棧
int tail = stack.pop();//尾部出棧，並刪除該元素
tail = stack.peek();//尾部出棧，不刪除該元素
/<integer>/<integer>
集合
集合是指具有某種特定性質的具體的或抽象的對象彙總成的集體，這些對象稱為該集合的元素，其主要特性是元素不可重複。
在Java中，HashSet 體現了這種數據結構，而HashSet是在MashMap的基礎上構建的。LinkedHashSet繼承了HashSet，使用HashCode確定在集合中的位置，使用鏈表的方式確定位置，所以有順序。TreeSet實現了SortedSet 接口，是排好序的集合（在TreeMap 基礎之上構建），因此查找操作比普通的Hashset要快（log(N)）；插入操作要慢（log（N））,因為要維護有序。
HashSet<integer> integerHashSet = new HashSet<>();
integerHashSet.add(12121);//添加
integerHashSet.contains(121);//是否包含
integerHashSet.size();//集合大小
integerHashSet.isEmpty();//是否為空
/<integer>
散列表
散列表也叫哈希表，是根據關鍵鍵值(Keyvalue)進行訪問的數據結構，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函數叫做散列函數。
Java中HashMap實現了散列表，而Hashtable比它多了一個線程安全性，但是由於使用了全局鎖導致其性能較低，所以現在一般用ConcurrentHashMap來實現線程安全的HashMap（類似的，以上的數據結構在最新的java.util.concurrent的包中幾乎都有對應的高性能的線程安全的類）。TreeMap實現SortMap接口，能夠把它保存的記錄按照鍵排序。LinkedHashMap保留了元素插入的順序。WeakHashMap是一種改進的HashMap，它對key實行“弱引用”，如果一個key不再被外部所引用，那麼該key可以被GC回收，而不需要我們手動刪除。
HashMap<integer> hashMap = new HashMap<>();
hashMap.put(1,"asdsa");//添加
hashMap.get(1);//獲得
hashMap.size();//元素個數
/<integer>
樹
樹（tree）是包含n（n>0）個節點的有窮集合，其中：
每個元素稱為節點（node）；
有一個特定的節點被稱為根節點或樹根（root）。
除根節點之外的其餘數據元素被分為m（m≥0）個互不相交的結合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹這種數據結構在計算機世界中有廣泛的應用，比如操作系統中用到了紅黑樹，數據庫用到了B+樹，編譯器中的語法樹，內存管理用到了堆（本質上也是樹），信息論中的哈夫曼編碼等等等等，在Java中TreeSet和TreeMap用到了樹來排序（二分查找提高檢索速度），不過一般都需要程序員自己去定義一個樹的類，並實現相關性質，而沒有現成的API。下面就用Java來實現各種常見的樹。
二叉樹
二叉樹是一種基礎而且重要的數據結構，其每個結點至多隻有二棵子樹，二叉樹有左右子樹之分，第i層至多有2^(i-1)個結點（i從1開始）；深度為k的二叉樹至多有2^(k)-1)個結點，對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。
二叉樹的性質：
1) 在非空二叉樹中，第i層的結點總數不超過2^(i-1), i>=1;
2) 深度為h的二叉樹最多有2^h-1個結點(h>=1)，最少有h個結點;
3) 對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1;
4) 具有n個結點的完全二叉樹的深度為log2(n+1);
5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關係：
若I為結點編號則 如果I>1，則其父結點的編號為I/2；
如果2I<=N，則其左兒子（即左子樹的根結點）的編號為2I；若2I>N，則無左兒子；
如果2I+1<=N，則其右兒子的結點編號為2I+1；若2I+1>N，則無右兒子。
6)給定N個節點，能構成h(N)種不同的二叉樹，其中h(N)為卡特蘭數的第N項，h(n)=C(2*n, n)/(n+1)。
7)設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i。
滿二叉樹、完全二叉樹
滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點；
完全二叉樹：若設二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結點數都達到最大個數，第h層所有的結點都連續集中在最左邊，這就是完全二叉樹；
滿二叉樹是完全二叉樹的一個特例。
二叉查找樹
二叉查找樹，又稱為是二叉排序樹（Binary Sort Tree）或二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
1) 若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2) 若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
3) 左、右子樹也分別為二叉排序樹；
4) 沒有鍵值相等的節點。
二叉查找樹的性質：對二叉查找樹進行中序遍歷，即可得到有序的數列。
二叉查找樹的時間複雜度：它和二分查找一樣，插入和查找的時間複雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間複雜度。原因在於插入和刪除元素的時候，樹沒有保持平衡。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是平衡二叉樹設計的初衷。
二叉查找樹可以這樣表示：
public class BST, Value> {
private Node root; // 根節點
private class Node {
private Key key; // 排序的間
private Value val; // 相應的值
private Node left, right; // 左子樹，右子樹
private int size; // 以該節點為根的樹包含節點數量
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
public BST() {}
public int size() {//獲得該二叉樹節點數量
return size(root);
}
private int size(Node x) {獲得以該節點為根的樹包含節點數量
if (x == null) return 0;
else return x.size;
}
}
查找：
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {//在以x節點為根的樹中查找key
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);//遞歸左子樹查找
else if (cmp > 0) return get(x.right, key);//遞歸右子樹查找
else return x.val;//找到了
}
插入：
public void put(Key key, Value val) {
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {在以x節點為根的樹中查找key，val
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);//遞歸左子樹插入
else if (cmp > 0) x.right = put(x.right, key, val);//遞歸右子樹插入
else x.val = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
刪除：
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) return x;
else return min(x.left);
}
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {//刪除以x為根節點的子樹最小值
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key) {
root = delete(root, key);
}
private Node delete(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);//遞歸刪除左子樹
else if (cmp > 0) x.right = delete(x.right, key);//遞歸刪除右子樹
else { //該節點就是所要刪除的節點
if (x.right == null) return x.left;//沒有右子樹，把左子樹掛在原節點父節點上
if (x.left == null) return x.right;//沒有左子樹，，把右子樹掛在原節點父節點上
Node t = x;//用右子樹中最小的節點來替代被刪除的節點，仍然保證樹的有序性
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.size = size(x.left) + size(x.right) + 1;
return x;
}
平衡二叉樹
平衡二叉樹又被稱為AVL樹，具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。它的出現就是解決二叉查找樹不平衡導致查找效率退化為線性的問題，因為在刪除和插入之時會維護樹的平衡，使得查找時間保持在O(logn)，比二叉查找樹更穩定。
ALLTree 的 Node 由 BST 的 Node 加上 private int height; 節點高度屬性即可，這是為了便於判斷樹是否平衡。
維護樹的平衡關鍵就在於旋轉。對於一個平衡的節點，由於任意節點最多有兩個兒子，因此高度不平衡時，此節點的兩顆子樹的高度差2.容易看出，這種不平衡出現在下面四種情況：
1、6節點的左子樹3節點高度比右子樹7節點大2，左子樹3節點的左子樹1節點高度大於右子樹4節點，這種情況成為左左。
2、6節點的左子樹2節點高度比右子樹7節點大2，左子樹2節點的左子樹1節點高度小於右子樹4節點，這種情況成為左右。
3、2節點的左子樹1節點高度比右子樹5節點小2，右子樹5節點的左子樹3節點高度大於右子樹6節點，這種情況成為右左。
4、2節點的左子樹1節點高度比右子樹4節點小2，右子樹4節點的左子樹3節點高度小於右子樹6節點，這種情況成為右右。
從圖2中可以可以看出，1和4兩種情況是對稱的，這兩種情況的旋轉算法是一致的，只需要經過一次旋轉就可以達到目標，我們稱之為單旋轉。2和3兩種情況也是對稱的，這兩種情況的旋轉算法也是一致的，需要進行兩次旋轉，我們稱之為雙旋轉。
單旋轉是針對於左左和右右這兩種情況，這兩種情況是對稱的，只要解決了左左這種情況，右右就很好辦了。圖3是左左情況的解決方案，節點k2不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的左子樹X子樹，所以屬於左左情況。
為使樹恢復平衡，我們把k1變成這棵樹的根節點，因為k2大於k1，把k2置於k1的右子樹上，而原本在k1右子樹的Y大於k1，小於k2，就把Y置於k2的左子樹上，這樣既滿足了二叉查找樹的性質，又滿足了平衡二叉樹的性質。
這樣的操作只需要一部分指針改變，結果我們得到另外一顆二叉查找樹，它是一棵AVL樹，因為X向上一移動了一層，Y還停留在原來的層面上，Z向下移動了一層。整棵樹的新高度和之前沒有在左子樹上插入的高度相同，插入操作使得X高度長高了。因此，由於這顆子樹高度沒有變化，所以通往根節點的路徑就不需要繼續旋轉了。
代碼：
private int height(Node t){
return t == null ? -1 : t.height;
}
//左左情況單旋轉
private Node rotateWithLeftChild(Node k2){
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k1.size = k2.size;
k2.size = size(k2.right)+size(k2.left)+1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
return k1; //返回新的根
}
//右右情況單旋轉
private Node rotateWithRightChild(Node k2){
Node k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k1.size = k2.size;
k2.size = size(k2.right)+size(k2.left)+1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.right), k2.height) + 1;
return k1; //返回新的根
}
雙旋轉是針對於左右和右左這兩種情況，單旋轉不能使它達到一個平衡狀態，要經過兩次旋轉。同樣的，這樣兩種情況也是對稱的，只要解決了左右這種情況，右左就很好辦了。圖4是左右情況的解決方案，節點k3不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的右子樹k2子樹，所以屬於左右情況。
為使樹恢復平衡，我們需要進行兩步，第一步，把k1作為根，進行一次右右旋轉，旋轉之後就變成了左左情況，所以第二步再進行一次左左旋轉，最後得到了一棵以k2為根的平衡二叉樹樹。
代碼：
//左右情況
private Node doubleWithLeftChild(Node k3){
try{
k3.left = rotateWithRightChild(k3.left);
}catch(NullPointerException e){
System.out.println("k.left.right為："+k3.left.right);
throw e;
}
return rotateWithLeftChild(k3);
}
//右左情況
private Node doubleWithRightChild(Node k3){
try{
k3.right = rotateWithLeftChild(k3.right);
}catch(NullPointerException e){
System.out.println("k.right.left為："+k3.right.left);
throw e;
}
return rotateWithRightChild(k3);
}
AVL查找操作與BST相同，AVL的刪除與插入操作在BST基礎之上需要檢查是否平衡，如果不平衡就要使用旋轉操作來維持平衡:
private Node balance(Node x) {
if (balanceFactor(x) < -1) {//右邊高
if (balanceFactor(x.right) > 0) {//右左
x.right = rotateWithLeftChild(x.right);
}
x = rotateWithRightChild(x);
}
else if (balanceFactor(x) > 1) {//左邊高
if (balanceFactor(x.left) < 0) {//左右
x.left = rotateWithRightChild(x.left);
}
x = rotateWithLeftChild(x);
}
return x;
}
private int balanceFactor(Node x) {
return height(x.left) - height(x.right);
}
堆
堆是一顆完全二叉樹，在這棵樹中，所有父節點都滿足大於等於其子節點的堆叫大根堆，所有父節點都滿足小於等於其子節點的堆叫小根堆。堆雖然是一顆樹，但是通常存放在一個數組中，父節點和孩子節點的父子關係通過數組下標來確定。如下圖的小根堆及存儲它的數組：
值：7,8,9,12,13,11
數組索引：0,1,2,3, 4, 5
通過一個節點在數組中的索引怎麼計算出它的父節點及左右孩子節點的索引：
public int left(int i) {
return (i + 1) * 2 - 1;
}
public int right(int i) {
return (i + 1) * 2;
}
public int parent(int i) {
// i為根結點
if (i == 0) {
return -1;
}
return (i - 1) / 2;
}
維護大根堆的性質：
public void heapify(T[] a, int i, int heapLength) {
int l = left(i);
int r = right(i);
int largest = -1;
//尋找根節點及其左右子節點，三個元素中的最大值
if (l < heapLength && a[i].compareTo(a[l]) < 0) {
largest = l;
} else {
largest = i;
}
if (r < heapLength && a[largest].compareTo(a[r]) < 0) {
largest = r;
}
// 如果i處元素不是最大的，就把i處的元素與最大處元素交換，使得i處元素變為最大的
if (i != largest) {
T temp = a[i];
a[i] = a[largest];
a[largest] = temp;
// 交換元素後，以a[i]為根的樹可能不在滿足大根堆性質，於是遞歸調用該方法
heapify(a, largest, heapLength);
}
}
構造堆：
public void buildHeap(T[] a, int heapLength) {
//從後往前看lengthParent處的元素是第一個有子節點的元素，所以從它開始，進行堆得維護
int lengthParent = parent(heapLength - 1);
for(int i = lengthParent; i >= 0; i--){
heapify(a, i, heapLength);
}
}
堆的用途：堆排序，優先級隊列。此外由於調整代價較小，也適合實時類型的排序與變更。
閱讀更多 Java從算法到架構 的文章
