数据需要一块连续的内存空间来存储，对内存的要求比较高。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。
最常见的链表：单链表、双链表、和循环链表。
单链表
结点：除了存储数据之外，还要记录链上的下一个节点的地址，如下图，我们把这个记录下个结点地址的指针叫作后继指针 next
头结点：用来记录链表的基地址。尾结点：指向一个空地址NULL
针对链表的插入和删除操作，只需考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。
链表想要随机访问第k个元素，就没有数组那么高效，链表的数据并非连续存储的，所以无法像数组那样，根据首地址和下标通过寻址公式就能直接计算出对应的内存地址，而是要根据指针一个结点一个结点的一次遍历，直到找到相应的结点。需要O(n)时间复杂度。
循环链表是一种特殊的单链表。它和单链表唯一的区别就在尾结点。循环链表的尾结点指针是指向链表的头结点。
当处理的数据具有环形结构特点时，就特别适合采用循环链表。
双向链表
双向链表支持双向遍历，它需要额外的两个空间来存储后继结点和前驱结点的地址。
时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。
数组缺点
- 若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
- 大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。
链表缺点
- 内存空间消耗更大，因为需要额外的空间存储指针信息。
- 对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。
缓存淘汰策略：
先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used）。
基于链表实现最近最少使用策略：
1.如果此数据之前已经被缓存进链表中，我们遍历得到这个数据对应的结点，将其从原来的位置删除，然后再插入到链表的头部。
2.如果此数据没有在缓存链表中，分两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部；
- 如果此时缓存已满，则将链表的尾结点删除，将新的结点插入到链表的头部。
这种实现思路，缓存的访问的时间复杂度未O(n).
我们可以引入散列表（Hash table）来记录每个数据的位置，将缓存的访问的时间复杂度降到O(1).
理解指针和引用的含义：
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的地址，指向了这个变量，通过指针就能找到这个变量。
警惕指针丢失和内存泄漏
p->next = x; // 将 p 的 next 指针指向 x 结点； x->next = p->next; // 将 x 的结点的 next 指针指向 b 结点；
p->next指针在完成第一步操作之后，已经不在指向结点b了，而是指向结点x，第二行代码相当于把x赋值给x->next,自己指向自己。整个链表断成了两半，从结点b往后的所有结点都无法访问了。
插入结点时，一定要注意操作顺序，把上面的两行换一个位置即可。
利用哨兵简化实现难度