06链表（上）：如何实现LRU缓存淘汰算法.pdfVIP

06|链表（上）：如何实现LRU缓存淘汰算法? 06|链表（上）：如何实现LRU缓存淘汰算法? “ Linked list ” LRU 今天我们来聊聊 链表（ ） 这个数据结构。学习链表有什么用呢？为了回答这个问题，我们先来讨论一个经典的链表应用场景，那就是 缓存淘汰算 法。 CPU 缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 缓存、数据库缓存、浏览器缓存等等。 缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策 FIFO First In First Out LFU Least Frequently Used LRU Least Recently Used 略 （ ， ）、最少使用策略 （ ）、最近最少使用策略 （ ）。 这些策略你不用死记，我打个比方你很容易就明白了。假如说，你买了很多本技术书，但有一天你发现，这些书太多了，太占书房空间了，你要做个大扫除，扔 掉一些书籍。那这个时候，你会选择扔掉哪些书呢？对应一下，你的选择标准是不是和上面的三种策略神似呢？ 好了，回到正题，我们今天的开篇问题就是：如何用链表来实现LRU缓存淘汰策略呢？带着这个问题，我们开始今天的内容吧！ 五花八门的链表结构 相比数组，链表是一种稍微复杂一点的数据结构。对于初学者来说，掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构，我们常常将会放到 一块儿来比较。所以我们先来看，这两者有什么区别。 我们先从底层的存储结构上来看一看。 为了直观地对比，我画了一张图。从图中我们看到，数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存 中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败。 而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是100MB大小的链表，根本不会有问 题。 file:///F/temp/geektime/数据结构与算法之美/06链表（上）：如何实现LRU缓存淘汰算法.html[2019/1/15 15:37:13] 06|链表（上）：如何实现LRU缓存淘汰算法? 链表结构五花八门，今天我重点给你介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。 我们刚刚讲到，链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数 据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针next。 file:///F/temp/geektime/数据结构与算法之美/06链表（上）：如何实现LRU缓存淘汰算法.html[2019/1/15 15:37:13] 06|链表（上）：如何实现LRU缓存淘汰算法? 从我画的单链表图中，你应该可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最 后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而 是指向一个空地址NULL ，表示这是链表上最后一个结点。 与数组一样，链表也支持数据的查找、插入和删除操作。 O(n) 我们知道，在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂