链表
一组任意的存储单元存储线性表存储元素，可以线性也不可不线性，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串。
单链表
我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
随机访问O(n)
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。
而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
双向链表
循环链表
插入和删除O(1)
双向循环链表
总结：
链表适合插入和删除 不适合随机访问 和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。不过，在具体软件开发中，要对数组和链表的各种性能进行对比，综合来选择使用两者中的哪一个
链表代码的书写
- 要注意链表指针丢失和内存泄漏
x->next=p->next
p->next=x
利用哨兵简化实现难度
new_node->next = p->next;
p->next = new_node;
然后有两种情况
1、空头，也就是第一个头结点是空的 可以存储数据的
但是，当我们要向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中 head 表示链表的头结点。所以，从这段代码，我们可以发现，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。
if (head == null) {
head = new_node;
}
2、非空头
删除
if (head->next == null) {
head = null;
}
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
代码：https://github.com/saber/algorithm/blob/master/src/list/single_list.hpp
