如何用链表实现LRU缓存淘汰算法？
缓存
- 缓存定义：一种高效数据读取性能的技术，比如常见的CPU缓存、数据库缓存、浏览器缓存等。缓存在计算机软件、硬件开发中应用都很广。
- 缓存特点：大小有限，被用满时，需要清理一部分数据，而哪些数据应该被清理哪些应该被保留，由
缓存淘汰策略决定。
缓存淘汰策略
常见的缓存淘汰策略有：FIFO（First in,First out）先进先出策略、LFU（Least Frequently Used）最少使用策略、LRU（Least Recently Used）最近最少使用策略。
三种链表
链表通过指针将一组零散的内存块串联在一起。其中内存块叫做链表的结点，记录结点地址的叫做指针。链表的第一个结点叫头结点，最后一个结点叫尾结点。
单链表
单链表的“尾结点”，它的指针并不指向下一个结点，而是指向一个空地址NULL
单链表插入和删除操作，复杂度为O(1)
循环链表
一种特殊的单链表，与单链表的区别就在于尾结点，其尾结点指向链表的头结点
相比于单链表，循环链表的优势在于从链尾到链头很方便。著名的约瑟夫问题，就适合这种数据结构。
双向链表
单链表只有一个方向，结点只有一个后继指针next指向后面的节点。双向链表有两个方向，一个后继指针next和一个前驱指针pre。
双向链表在某些情况下的插入、删除操作比单链表更高效。
例如删除操作，从链表中删除一个数据，有两种情况：
- 删除链表中值等于某个给定值的结点
- 删除给定指针指向的结点
对于第一种情况，无论单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再将其删除。
尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
对于第二种情况，已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点。这种情况下单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要 O(1) 的时间复杂度。
以上的情况涉及到一个空间换时间的设计思想：双向链表更费内存，但仍比单链表应用更广泛。
缓存实际上就是利用了空间换时间的设计思想。
如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。
但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。
若内存空间充足，如果更加追求代码的执行速度，就选择空间复杂度相对较高，时间复杂度相对较低的算法和数据结构，例如，缓存技术。
若内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间。
数组与链表对比
时间复杂度
删除、插入：链表O(1)、数组O(n)
随机访问操作：链表O(n)、数组(1)
缓存支持
数组在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。
链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
原因
CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取要访问的地址，而是读取一个数据块，并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。
这样就实现了比内存访问速度更快的机制，也是CPU缓存存在的意义：为了弥补内存访问速度过慢与CPU执行速度快之间的差异。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。
灵活性
数组大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致内存不足（out of memory）。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。
链表本身没有大小的限制，天然地支持动态扩容。
链表实现LRU缓存淘汰策略的思路
维护一个有序单链表，越靠近链表尾部的结点是越早被访问过的。当有新的数据被访问时，从链表头开始顺序遍历链表。----缓存访问的时间复杂度为O(n)
过程：
1 . 当访问的数据存储在缓存的链表中时，遍历得到数据对应的结点，将其从原位置删除，再将其插入到链表表头；
2 . 当访问的数据未出现在缓存的链表中时
1）若缓存有空闲，将该数据直接插入到链表表头。
2）若缓存被占满，则将链表尾部的数据删除，再将新数据插入到链表表头。
优化：使用散列表，记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。
思考
如何用数组实现LRU缓存淘汰策略？
方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时
1）缓存有空闲，将数据插入数组第一个元素位置，数组所有元素需要向后移动1个位置，新数据插入数组第一个元素位置，时间复杂度为O(n)；
2）缓存无空闲，清理数组末尾位置的元素，数组所有元素需要向后移动1个位置，新数据插入数组第一个元素位置，时间复杂度为O(n)；
当访问的数据存在于缓存的数组中时，查找到数据，将其从原位置删除，并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。
方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时
1）缓存有空闲，直接将数据添加进数组作为当前最后一个元素，时间复杂度为O(1)；
2）缓存无空闲，清理数组首位置的元素，数组所有元素向前移动1个位置， 将新元素插入数组，时间复杂度为O(n)；
当访问的数据存在于缓存的数组中时，查找到数据，将其从原位置删除，并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。
优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。
如何通过单链表实现“判断某个字符串是否为回文字符串”？
比如 “123454321”
1 . 前提：字符串以单个字符的形式存储在单链表中。
2 . 遍历链表，判断字符个数是否为奇数，若为偶数，则不是。
3 . 将链表中的字符倒序存储一份在另一个链表中。
4 . 同步遍历2个链表，比较对应的字符是否相等，若相等，则是回文字符串，否则，不是。