链表定义
链表（Linked list）是一种线性，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)
链表包含了内存块”节点”，以及记录下个或者上个节点地址的指针next。
链表常见结构
单向链表
- 第一个节点称之为头节点，头结点不存放数据，最后一个称之为尾节点。
- 每个节点分为两个部分。第一个部分是保存活显示关于节点的信息，第二个部分是存储下一个节点的地址。
- 单链表只能单方向遍历，且最后尾节点的下一个地址指针指向为NULL。
循环链表
- 首尾节点连接在一起，可以是单链表的首尾相连，也可以是双链表的首尾相连。
双向链表
- 双向链表有两个连接，一个指向前一个节点(若是头节点，则指向NULL)，另外一个指向下一个节点(若是尾节点，则指向NULL)。
链表的查找、插入、删除
插入删除行为复杂度
- 对于数组而言，因为需要保证内存空间的连续性，当插入或者删除的时候，需要对数据进行搬迁(比如插入第二个位置，则原本第二个位置的数据”搬迁”到第三个位置，原本第三个位置的数据”搬迁”到第四个位置，以此类推)，这样才能保证连续,所以其时间复杂度为O(n)。
- 对链表而言，因为无需考虑数据的搬迁，只需要改变前后节点指针，所以其时间复杂度为O(1)。
查询行为复杂度
- 数组查询分两种，一种是根据下标索引查询，一种是查询具体数据，如果是第一种，则可以通过首地址和下标通过寻址公式查询得到，时间复杂度为O(1)，但第二种查询具体数据，则是O(n)。
- 链表的查询则因为需要依次遍历，所以其查询复杂度为O(n)。
链表和数组
- 数组需要一块连续的内存空间。如果连续空间不足以被申请，即便总内存足够，也会创建数组失败。
- 链表不需要连续的内存空间，他通过指针将一组零散的内存块串联起来。
- 链表因为需要额外对指针进行存储，所以内存空间使用比数组要大。
- cpu从内存读取数据，会先把读取到的数据加载到cpu的缓存中。从内存读取数据并不只是读取特定的访问地址，而是一个的数据块并存入cpu缓存中，然后下次查询的时候会先从cpu缓存中查询，如果找不到就从内存中查询，对于数组，读取某个下标对应的值后，其因为是连续的内存，所以会被一并存入cpu缓存中，而链表不会。
refer
https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8
https://www.cnblogs.com/springfor/p/3985333.html
https://time.geekbang.org/
