【算法打卡60天】Day4链表（上）：如何实现LRU缓存淘汰算法

打卡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. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

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