数组：
优势：随机访问速度快，即 int[] array={3,6,9,7,4} 可以使用array[下标] 随便访问第任意个元素，而链表只能访问相邻元素，顺序访问。单向链表、双向链表原理
区别： 表头为空，表头指向后续第一个节点，第一个节点指向第二个节点，由此类推。每一个节点依次指向下一个节点。 双向链表每个节点指向前后2个节点。实现（java，部分功能实现）
public class DoubleLinkList{ private int mCount; private DNode mHead; </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> DoubleLinkList() { mHead </span>= <span style="color: #0000ff;">new</span> DNode<>(<span style="color: #0000ff;">null</span>, <span style="color: #0000ff;">null</span>, <span style="color: #0000ff;">null</span><span style="color: #000000;">); mHead.prev </span>= mHead.next =<span style="color: #000000;"> mHead; mCount </span>= <span style="color: #800080;">0</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> size() { </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> mCount; } </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> boolean isEmpty() { </span><span style="color: #0000ff;">return</span> <span style="color: #0000ff;">this</span>.mCount == <span style="color: #800080;">0</span><span style="color: #000000;">; } </span><span style="color: #008000;">/*</span><span style="color: #008000;">* * 获取第index的节点 * * @param index * @return </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">public</span> DNode<T> getNode(<span style="color: #0000ff;">int</span><span style="color: #000000;"> index) { </span><span style="color: #0000ff;">if</span> (index < <span style="color: #800080;">0</span> || index >=<span style="color: #000000;"> mCount) { </span><span style="color: #0000ff;">throw</span> <span style="color: #0000ff;">new</span><span style="color: #000000;"> IndexOutOfBoundsException(); } </span><span style="color: #008000;">//</span><span style="color: #008000;">看节点所在位置，判断是否正向查找</span> <span style="color: #0000ff;">if</span> (index <= mCount / <span style="color: #800080;">2</span><span style="color: #000000;">) { DNode</span><T> node =<span style="color: #000000;"> mHead.next; </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>; i < index; i++<span style="color: #000000;">) { node </span>=<span style="color: #000000;"> node.next; } </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> node; } DNode</span><T> rnode =<span style="color: #000000;"> mHead.prev; </span><span style="color: #0000ff;">int</span> rindex = mCount - index - <span style="color: #800080;">1</span><span style="color: #000000;">; </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">0</span>; j < rindex; j++<span style="color: #000000;">) { rnode </span>=<span style="color: #000000;"> rnode.prev; } </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> rnode; } </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> T getFirst() { </span><span style="color: #0000ff;">return</span> getNode(<span style="color: #800080;">0</span><span style="color: #000000;">).value; } </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> T getLast(){ </span><span style="color: #0000ff;">return</span> getNode(mCount-<span style="color: #800080;">1</span><span style="color: #000000;">).value; } </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">void</span> insert(<span style="color: #0000ff;">int</span><span style="color: #000000;"> index,T t) { </span><span style="color: #0000ff;">if</span>(index==<span style="color: #800080;">0</span><span style="color: #000000;">) { DNode</span><T> node=<span style="color: #0000ff;">new</span> DNode<><span style="color: #000000;">(t,mHead,mHead.next); mHead.next.prev</span>=<span style="color: #000000;">node; mHead.next</span>=<span style="color: #000000;">node; mCount</span>++<span style="color: #000000;">; </span><span style="color: #0000ff;">return</span><span style="color: #000000;">; } DNode</span><T> inode=<span style="color: #000000;">getNode(index); DNode</span><T> tnode=<span style="color: #0000ff;">new</span> DNode<><span style="color: #000000;">(t,inode.prev,inode); inode.prev.next</span>=<span style="color: #000000;">tnode; inode.next</span>=<span style="color: #000000;">tnode; mCount</span>++<span style="color: #000000;">; </span><span style="color: #0000ff;">return</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> insertFirst(T t){ insert(</span><span style="color: #800080;">0</span><span style="color: #000000;">,t); } </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> appendLast(T t) { DNode</span><T> node=<span style="color: #0000ff;">new</span> DNode<><span style="color: #000000;">(t,mHead.prev,mHead); mHead.prev.next</span>=<span style="color: #000000;">node; mHead.prev</span>=<span style="color: #000000;">node; mCount</span>++<span style="color: #000000;">; } </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">class</span> DNode<T><span style="color: #000000;"> { </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> DNode prev; </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> DNode next; </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> T value; </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> DNode(T value, DNode prev, DNode next) { </span><span style="color: #0000ff;">this</span>.prev=<span style="color: #000000;">prev; </span><span style="color: #0000ff;">this</span>.next=<span style="color: #000000;">next; </span><span style="color: #0000ff;">this</span>.value=<span style="color: #000000;">value; } }}
实现中参考jdk的LinkedList实现，看到了静态内部类，回顾一下静态内部类的用法。即，当类的外部类需要使用该类，而静态内部类本身不需要引用外部成员，并且静态内部类可以单独初始化的场景下使用。
递归算法
通俗概念：递归算法就是直接或间接调用自己的算法。二叉树概念
树可以分为 完美二叉树（perfect Binary tree）：除了叶子结点之外的每一个结点都有2个孩子，每一层都被完全填充。完全二叉树（complete Binary tree）：除了最后一层之外的每一层都被完全填充，并且所有结点都保持向左对齐。
完满二叉树（full Binary tree）：除了叶子结点之外的每一个结点都有2个孩子的结点。