邯郸移动网站建设报价,做网页收集素材常用的网站有哪些,天堂 最新版中文在线,wordpress幻灯片回收站在哪里文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
底层存储
数组#xff1a;一块连续的内存空间。 链表#xff1a;用指针串起来的一组零散的内存空间。 链表分类#xff1a;单链表、双向链表、循环链表
单链表…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
底层存储
数组一块连续的内存空间。 链表用指针串起来的一组零散的内存空间。 链表分类单链表、双向链表、循环链表
单链表
内存块是连接的节点。每个节点存储数据和指向下一个节点的指针。第一个节点叫做头结点最后一个节点叫做尾节点。尾节点的nextnull。
操作特点
1 插入、删除很快O(1)。 2 想要随机访问只能从头节点开始遍历数到第k个节点。平均时间复杂度O(n)。想象队列就是一个排队的队伍。每个人只知道自己后面的那个人。
循环链表
结构特点循环列表的尾节点指向链表的头结点。 用途用于解决数据具有环形结构的问题。例如约瑟夫问题。
双向链表
双向链表的节点存储数据指向下一个节点的指针指向上一个节点的指针。
用途1更方便的插入删除
删除的使用场景一般为给定一个值将具有这个值得节点删除。只是删除需要O(1)的时间但是查询的平均时间复杂度为O(n)。根据时间复杂度的加法原则时间复杂度为O(n)。 另外一个场景是已经给定一个节点删除这个节点。单项链表因为没有向前的指针所以需要从头开始遍历找到要删除节点的前一个节点。平均时间复杂度(O(n))。如果是双向列表因为有向前的指针O(1)就可以实现。
在某个节点前插入一个元素双向列表显示出了优势因为有前向指针。时间为O(1)。
用途2在有序列表中查找更方便
因为每次查询时都要比较当前元素和要找元素的大小然后决定向前走还是向后走。
链表 VS 数组
在时间复杂度方面 数组插入、删除 O(n) 随机访问O(1) 链表插入、删除O(1)随机访问 O(n)
数组的优点数组更简单可以利用CPU缓存速度更快。 数组的缺点需要申请固定大小的空间在扩容的时候更加浪费内存可能产生OOM。
链表的优点大小可以是不固定的。 链表的缺点内存块是不连续的不能利用CPU缓存。
思考题如何基于链表给出LRU缓存
LRU缓存是指删除最近访问少的元素 的缓存策略。 已经访问过的元素用链表存储。现在假设访问元素a有如下情况 1 a在链表中那把a元素删除插入在队列头部作为头结点。 2 a不在链表中 2.1 并且链表空间充足则把a插入在链表头部。 2.2 并且链表空间不足则把尾元素删除把a插入在链表头部。 因为要遍历每个元素所以平均时间复杂度是O(n)。如果使用散列表就能提高速度。
写好链表代码的几个技巧
1 理解指针的含义。将某个变量赋值给指针实际上就是将这个变量的地址赋值给指针。 2 警惕指针丢失和内存泄漏 3 利用哑结点简化代码 4 留意边界条件的处理。链表可以考虑的几个边界条件有 4.1 如果列表为空代码可以正常运行吗 4.2 如果列表只包含一个节点代码可以正常运行吗 4.2 如果列表含2个节点代码可以正常运行吗 4.3 代码逻辑在处理头、尾节点的时候代码可以正常运行吗
5 举例画图帮助思考 6 多写多练
关于链表面试中经常遇到的场景
1 单链表翻转 2 是否有环检测 3 2个有序链表合并 4 删除倒数第k个节点 5 求中间节点
