### 概述 动态数组,栈,队列底层都是依托于静态数组,靠resize解决固定容量问题.而链表是真正的动态数据结构. * 链表是最简单的动态数据结构. * 更深入的理解引用(或者指针). * 更深入的理解递归. * 辅助组成其他数据结构 . ### 链表Linked list * 数据存储在"节点"(Node)中,当一个节点的next是NULL,那么这个节点就是最后一个节点.  * 优点:真正的动态,不需要处理固定容量的问题.需要多少的数据,就生成多少个节点. * 缺点:丧失了随机访问的能力. ### 数组和链表的对比 #### 数组 * 数组对号用于索引有语意的情况 . scores[2] * 最大优点:支持快速查询. #### 链表 * 链表不适合用于索引有语意的情况. * 最大优点:动态. ### 向链表中添加元素 和数组不同,数组在尾部添加元素比较方便,而链表是在头部添加元素比较方便 . #### 在链表头添加元素  #### 为链表设立虚拟头结点 在向链表头添加元素和在链表其他位置添加元素逻辑上会有差别,为什么对链表头添加元素会有差别呢?因为在向链表添加元素的时候,需要找到链表待添加位置之前的一个节点,但是对于链表头来说,它没有之前的一个节点. 这时候就需要虚拟的头结点了(dummyHead).这个dummyHead对用户来说是没有意义的,只是方便我们编写逻辑.当有了dummyHead之后我们就不要对头结点进行特殊的处理了.  #### 在链表中间添加元素  在链表中操作的顺序很重要  #### 链表元素的删除(需要虚拟头结点) 找到待删除元素之前的那个节点.  ### 时间复杂度 链表的增删改查的时间复杂度都是O(n)的,只对链表头操作是O(1) .对于链表来说,适合做的事情,不去修改,查也别查任意位置的元素,只查链表头,增加和删除也只对链表头进行操作.因为链表是动态的,所以不会占用大量的内存空间,具有一定的优势. #### 添加操作 * addLast(e) //O(n) * addFirst(e) //O(1) * add(index e) //O(n/2) = O(n) #### 删除操作 * removeLast(e) //O(n) * removeFirst(e) //O(1) * remove(index e) //O(n/2) = O(n) #### 修改操作 * set(index e) //O(n) #### 查找操作 链表中不用实现find()方法,因为就算拿到了索引,也没办法快速访问. * get(index) //O(n) * contains(e) //O(n)