美文网首页
【算法打卡60天】Day4链表(上):如何实现LRU缓存淘汰算法

【算法打卡60天】Day4链表(上):如何实现LRU缓存淘汰算法

作者: 花生无翼 | 来源:发表于2019-12-02 16:12 被阅读0次

    打卡Day4
    今天学习了第一阶段的链表(上):如何实现LRU缓存淘汰算法?
    今日收获:
    缓存通常有三种缓存淘汰策略
    常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。
    1.掌握链表基础知识
    最常用的是单链表,除了单链表还有循环链表和双向链表,循环链表是一种特殊的单链表。

    2.链表 VS 数组性能大比拼
    具体用哪种数据结构还需要具体问题具体分析。
    时间复杂度
    插入删除:数组O(n),链表O(1)
    随机访问:数组O(1),链表O(n)

    3.如何基于链表实现 LRU 缓存淘汰算法?

    1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
    2. 如果此数据没有在缓存链表中,又可以分为两种情况:如果此时缓存未满,则将此结点直接插入到链表的头部;如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

    本文由【极客时间】专栏《数据结构与算法之美》学习得来。

    相关文章

      网友评论

          本文标题:【算法打卡60天】Day4链表(上):如何实现LRU缓存淘汰算法

          本文链接:https://www.haomeiwen.com/subject/jflfgctx.html