最近最少使用策略的实现

LRU(Least Recently Used)

链表不需要一块连续的存储空间,使用零散的内存块,连接起来使用。

单链表

链表的每个节点除了需要存储数据以外,还需要存储下一个链表的指针位置,叫做next指针
单链表有两个特殊的节点,头节点和尾节点,头节点用来记录链表的基地址,尾节点的的指针指向空地址NULL,表示该节点是链表上的最后一个节点。

链表插入数据的时间复杂度是O(1),因为只需要改变前后节点的指针地址就可以了。但是查找需要O(n)的时间复杂度,因为每一个节点只知道下一个节点的地址。

循环链表

和单链表的区别在于,循环链表的尾节点的指针指向头节点。“收尾相连”,所以叫做循环链表。
循环链表的优点在于,从尾节点到头结点比较方便。

双向链表

双向链表和单链表不同的是,每一个节点除了有next指针以外,还具有一个prev指针,指向前一个节点的next指针位置。next指针指向下一个节点的prev指针

动态扩容

链表的存储结构使得原生具备动态扩容的特性。
链表通过增加额外的记录下一个节点的地址,优化了插入和删除的操作,利用了空间换时间的概念。相比较数组,链表消耗的存储资源会更多。

LRU 淘汰算法的实现原理

实现一个有序的单链表,越往后的是越早范围的数据。
当有一个新的数据进来的时候,查找这个数据在链表里面有没有,如果有的话,那么删除这个节点,并把这个节点插入到链表头部位置。

如果这个数据在链表里面没有,那么分两种情况:

  • 如果链表空间已满,那么删除最后一个元素,并将新的元素插入到头部的位置。
  • 如果链表空间没有满,则直接插入到头部的位置。

5个常见的链表操作

  • 单链表反转
  • 链表中环的检测
  • 两个有序链表的合并
  • 删除链表倒数第N个结点
  • 求链表的中间结点

写链表代码的六个技巧

  • 理解指针或引用的含义
  • 警惕指针丢失和内存泄露
  • 利用哨兵简化实现难度
  • 重点留意边界条件的处理
  • 画图举例,辅助思考
  • 多写多练