锐客网

  1. 首页 > it技术 > >

链表（如何实现LRU缓存淘汰算法）

链表：如何实现LRU缓存淘汰算法 一个经典的链表应用场景，就是LRU缓存淘汰算法
缓存是一种提高数据读取性能的技术，比如CPU缓存、数据库缓存、浏览器缓存等等
缓存的大小有限，当缓存被用满的时候哪些数据该被清理出去？哪些数据该被保留？需要缓存淘汰策略来决定：先进先出策略FIFO,最少使用策略LFU,最近最少使用策略LRU
数组需要一块连续的内存空间来存储，对内存的要求比较高，如果申请一个100M大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100M，仍然会申请失败，而链表不是，用过“指针”将一组零散的内存块串联起来使用，如果我们申请的是100M大小的链表，不会有问题。
单链表
链表通过指针将一组零散的内存块串联在一起，我们把内存块成为链表的结点，为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需记录链上的下一个结点的地址，叫做后继指针
第一个结点叫作头结点，最后一个叫作尾结点，头结点用来记录链表的基地址，可以遍历得到整条链表，尾结点指向一个空地址NULL，表示这是链表的最后一个结点
支持数据的查找、插入和删除操作：
针对链表的插入删除操作，只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)，但是链表想随机访问第k个元素，就没有数组高效，无法像数组一样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点依次遍历，直到找到相应的结点，需要O(n)的时间复杂度
循环链表
一个特殊的单链表，与单链表的唯一区别是在尾结点，循环链表的尾结点是指向链表的头结点
优点是从链尾到链头比较方便，当要处理的数据具有环形结构特点的时候，采用循环链表，比如约瑟夫问题
双向链表
支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址，所以如果存储同样多的数据，双向链表要比单链表占用更多的内存空间
双向链表支持O(1)时间复杂度的情况下找到前驱结点
链表的两个操作
删除操作：删除结点中“值等于某个给定值”的结点和删除给定指针指向的结点，第一种情况单链表和双向链表为了查找到值等于给定值的结点都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，再进行删除，耗时的时间复杂度总共是O(n)。第二章情况，已经找到了要删除的结点，但是删除某个结点q需要知道其前驱结点，单链表得从头结点开始遍历链表找到前驱结点，双向链表只需要在O(1)的时间复杂度内搞定
除了插入、删除操作双向链表有优势外，作为一个有序链表，双向链表的按值查询的效率也高，我们可以记录上次查找的位置p，每次查询时，根据要查找的值与P的大小比较，所以平均只需要查找一半的数据
缓存实际上就是利用了空间换时间的设计思想，我们可以通过缓存技术，事先将数据加载在内存中，虽然比较浪费内存空间，但是每次数据查询的速度大大提高。
对于执行比较慢的程序，可以通过消耗更多的内存(空间换时间)来进行优化
数组和链表作对比
数组和链表相比并不能局限于时间复杂度，数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高，链表在内存中并不是连续存储，对CPU缓存并不友好，没办法有效预读
链表本身没有大小的限制，天然支持动态扩容，是与数组的最大的区别
如何基于链表实现LRU缓存淘汰算法
一个有序单链表，越靠近链表尾部的结点是越早之前访问的，当有一个新的数据被访问时，我们从链表头开始顺序遍历链表
1.如果此数据之前已经被缓存在链表中，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部
2.如果此数据没有缓存链表中，又可以分为两种情况：
①此时缓存未满，则将此结点直接插入到链表的头部；
②此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部
实现了一个LRU缓存
缓存访问的时间复杂度是O(N),如果引入散列表来记录每个数据的位置，将缓存访问的时间复杂度降到O(1)
如何使用数组实现LRU缓存淘汰策略？
如何判断一个字符串是否是回文字符串？
如果字符串是通过单链表来存储的，如何判断是一个回文串？
使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步，快指针到达终点的时候，慢指针的位置就是链表中间结点，循环次数为链表除去中间结点后前后两组的长度，求得单向链表中间结点，并计算遍历次数，遍历次数就是半链表长度，在慢指针前进的过程中，同时修改其next指针，使得链表前半部分反序，最后比较中点两侧的链表是否相等
快慢指针定位中间结点，从中间结点对后半部分逆序，前后半部分比较，判断是否回文，后半部分逆序复原
【链表（如何实现LRU缓存淘汰算法）】看内存消耗多少，空间复杂度是O(1)

#include #include #define N 100int main() { char s[N]; int i,j,n,count=0; printf("Input a string:\n"); gets(s); n=strlen(s); for(i=0,j=n-1; i

#include #include int main() { char a[100]= {0}; int i = 0; int len = 0; printf("please input character string:\n"); gets(a); len = strlen(a); //计算输入字符串的长度；for(i = 0; i < (len / 2); i++) //只需要判断前一半（len/2）长度就好了 { if(a[i] != a[len - 1 - i]) //判断是否为回文数； { printf("不是回文数\n"); return 0; } }printf("是回文数\n"); return 0; }

    推荐阅读


    上一篇：java|Jsoup 抓取网页信息（2） 需要Login的网页信息抓取

    下一篇：Eclipse中@Data注解get、set错误