《数据结构与算法之美》学习02

数组和链表

数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。

而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

最常见的链表结构,它们分别是:单链表、双向链表和循环链表。

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

思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。

  2. 如果此数据没有在缓存链表中,又可以分为两种情况:

如果此时缓存未满,则将此结点直接插入到链表的头部;

如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

回文串

“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。

分享