数据结构与算法之美 : 链表

数据清理策略:

FIFO(First in , Filst out ) : 先入先出  

LFU( Least Frequently Used  )  : 最少使用

LRU(Least Recently Used ) : 最近最少使用

 

数组 : 需要连续的内存空间来存储, 如果内存中的内存空间连续的部分不满足需要的大小,会申请失败.

链表: 通过指针将一组 零散的内存块串联起来

 

 

链表种类: 单向 双向 循环 三种最常见.

 

 

单向链表

 

 

缺点: 随机访问,低效. 需要顺序查找.

 

循环链表

 

双向链表

 

 

 

链表 VS 数组性能大比拼

 

 

数组:

1. 使用的是连续的内存空间, CPU 可以利用缓存机制, 预读取数据,访问效率低. 
2. 大小固定,占用连续空间,数组过大, OOM .  数组扩容 费时. 
3. 随机访问性能高,占用空间比链表小.

 

 

 

链表:

1. 并不是连续存储, CPU 缓存不友好,无法预读.
2. 支持动态扩容.
3. 容易产生碎片,造成 GC

 

CPU 缓存机制

CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。

对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。

 

 

LRU 缓存淘汰思路

维护一个单向链表

方式一：首位置保存最新访问数据，末尾位置优先清理

方式二：首位置优先清理，末尾位置保存最新访问数据

 

 

 

还可以使用 散列表(Hash Table ) 来做.

 

将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。

 

顺序:

先将 x 的 next 指向 b. 然后再将 a的 next 指向 x.

 

针对链表的插入/删除操作,需要对插入第一个节点和删除最后一个节点做特殊处理.

 

带头链表:

有哨兵节点的链表叫带头链表. 哨兵节点是不存储数据的.

 

 

 

注意边界条件,防止边界异常.

 

 

 

 

 

 

 

 

 

 

总结:

 

1.如何分别用链表和数组实现LRU缓冲淘汰策略？
1）什么是缓存？
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
2）为什么使用缓存？即缓存的特点
缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。
3）什么是缓存淘汰策略？
指的是当缓存被用满时清理数据的优先顺序。
4）有哪些缓存淘汰策略？
常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。
5）链表实现LRU缓存淘汰策略
当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。
6）数组实现LRU缓存淘汰策略
方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。
方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）
2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如 上海自来水来自海上）
1）前提：字符串以单个字符的形式存储在单链表中。
2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。
3）将链表中的字符倒序存储一份在另一个链表中。
4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。
六、设计思想
时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

 

-------------    第二部分总结        -----------------------------

一、理解指针或引用的含义

1.含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。
2.示例：
p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

二、警惕指针丢失和内存泄漏（单链表）
1.插入节点
在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。
正确的写法是2句代码交换顺序，即：x—>next = p—>next; p—>next = x;
2.删除节点
在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;

三、利用“哨兵”简化实现难度
1.什么是“哨兵”？
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。
2.未引入“哨兵”的情况
如果在p节点后插入一个节点，只需2行代码即可搞定：
new_node—>next = p—>next;
p—>next = new_node;
但，若向空链表中插入一个节点，则代码如下：
if(head == null){
head = new_node;
}
如果要删除节点p的后继节点，只需1行代码即可搞定：
p—>next = p—>next—>next;
但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：
if(head—>next == null){
head = null;
}
从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。
3.引入“哨兵”的情况
“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。
4.“哨兵”还有哪些应用场景？
这个知识有限，暂时想不出来呀！但总结起来，哨兵最大的作用就是简化边界条件的处理。

四、重点留意边界条件处理
经常用来检查链表是否正确的边界4个边界条件：
1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个节点时，代码是否能正常工作？
3.如果链表只包含两个节点时，代码是否能正常工作？
4.代码逻辑在处理头尾节点时是否能正常工作？

五、举例画图，辅助思考
核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

六、多写多练，没有捷径
5个常见的链表操作：
1.单链表反转
2.链表中环的检测
3.两个有序链表合并
4.删除链表倒数第n个节点
5.求链表的中间节点

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

来源:

数据结构与算法之美   -- 王争