【数据结构&算法】06-链表类型及LRU算法
2021/11/5 11:10:45
本文主要是介绍【数据结构&算法】06-链表类型及LRU算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 前言
- 缓存
- 各种链表结构
- LRU 缓存淘汰算法
前言
个人认为链表是常用的基础数据结构之一。
李柱明博客:https://www.cnblogs.com/lizhuming/p/15487315.html
缓存
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
当缓存满时也有对应策略处理:
- 先进先出策略 FIFO(First In,First Out)。
- 最少使用策略 LFU(Least Frequently Used)。
- 最近最少使用策略 LRU(Least Recently Used)。
各种链表结构
相对于数组,链表的存储空间是非连续的,靠的是指针把各个数据连接起来。
链表的结构多种多样:
- 单向链表。
- 单向循环链表。
- 双向链表。
- 双向循环链表。
根据链表的数据结构,也可以分为通用链表和非通用链表。
参考:
- 双向通用链表
- 双向非通用链表
LRU 缓存淘汰算法
最近最少使用策略 LRU(Least Recently Used)。
数据管理思路:
-
主要思路:把当前使用的节点放到链表头。具体思路如下:
-
维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。
-
当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。
-
如果此数据之前已经被缓存在链表中了,遍历到这个数据对应的结点,将其从原来的位置删除,然后再插入到链表的头部。
-
如果此数据没有在缓存链表中:
- 缓存未满,则将此结点直接插入到链表的头部;
- 缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
-
这篇关于【数据结构&算法】06-链表类型及LRU算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)