✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。
✨博主学习方法
“三刷”官方文档或源码是我高效学习一门新的技能的制胜法宝:
1刷从头看到尾,扫清知识盲点,搞清楚概念;
2刷必须手敲,而且要写注释和总结;
3刷先只写注释,不看文档实现功能,遇到问题再和文档比较,加深理解。
✨前言
上篇我们总结了对数组的理解,这篇再谈谈对链表的理解。
本篇文章主要分析如下几个问题:
链表相对于数组而言,是两种不同的内存组织方式,链表不需要连续的内存空间,天然支持动态扩容,而且不像数组扩容那样需要搬运数据。链表大小等于实际使用大小,不存在浪费空间的现象。链表适合插入和删除操作,时间复杂度为O(1),但是并不意味着适合非常频繁地插入和删除,因为那样会导致频繁地申请内存和释放内存,容易造成内存碎片,从而提高GC的频率。
✨✨单向链表
每一块内存区域称为一个节点,每个节点有两块区域,数据域保存节点数据,指针域指向下一个节点的地址。其中,头节点是整个链表的基地址,通过它可以遍历整个链表;尾节点的指针值为空,不指向任何地址。
单链表比较适合插入和删除操作,时间复杂度为O(1),注意此处不包含查找到该元素的时间,但是查询操作效率较低,时间复杂度为O(n);
单链表结构示意
✨✨✨双向链表
每一块内存区域称为一个节点,每个节点有三块区域,前指针域指向上一个节点的地址,数据域保存节点数据,后指针域指向下一个节点的地址。和单向链表相比,存储相同多的数据,双向链表需要的存储空间更多。
双向链表的插入、删除和查询操作都要比单向链表的相同操作的效率更高:
因此,即便双向链表比较占用空间,但这是一种空间换时间的设计思想,使用场景反而比单向链表更多。
双向链表结构示意
✨✨✨✨循环链表
循环链表是一种特殊的单链表,区别是其尾节点的指针域不是空,而是指向头节点。其优点就是从链表尾部到链表头部比较方便,当我们需要处理环形结构的数据时,就比较合适。
循环链表结构示意
当然,将双向链表和循环链表组合起来,就能形成一个双向循环链表,这个用得不多,不赘述。
双向循环链表结构示意
✨✨✨✨✨使用链表实现LRU
常见的缓存淘汰策略有三种,FIFO(先进先出Firt In First Out)、LFU(最少使用Least Frequently Used)、LRU(最近最少使用Least Recently Used)。