昆山有名的网站建设公司seo关键词分析表
文章目录
- 链表（Linked List）
链表（Linked List）
- 定义：链表（Linked List）是一种线性表数据结构，他用一组任意的存储单元来存储数据，同时存储当前数据元素的直接后继元素所存放的内存地址。
- 操作
- 插入和删除操作时间复杂度为O(1)
- 随机访问第k个元素的时间复杂度为O(n)
- 单链表：
- 实现：数据域data+指针域next
- 循环链表：
- 实现：尾结点指针指向头结点
- 优点：支持时间复杂度O(1)找到头结点
- 双向链表：
- 实现：数据域data+指针域prior和next
- 优点：支持时间复杂度O(1)找到前驱结点
- 数组VS链表
- 时间复杂度
- 数组随机访问O(1)，插入删除O(n)
- 链表随机访问O(n)，插入删除O(1)
- 访问效率
- 数组使用连续内存空间实现，可以借助CPU缓存机制预读数据，访问效率更高；
- 链表在内存中非连续存储，对CPU缓存不友好，无法有效预读
- 空间
- 数组大小固定，声明时需要指定其大小，可能出现内存不足或者浪费情况
- 链表天然支持动态扩容，没有空间浪费情况
- 时间复杂度
- 应用：使用链表实现LRU缓存淘汰算法
- 缓存：一种提高数据读取性能的技术，广泛应用于硬件设计，软件开发，如CPU缓存，数据库缓存，浏览器缓存。缓存大小有限，当缓存满时，需要使用缓存淘汰策略决定哪些数据被清理，哪些数据被保留
- 缓存淘汰策略指当缓存满时数据的清理顺序，包括先进先出策略（FIFO），最少使用策略(Least Frequently Used, LFU)，最近最少使用策略(Least Recently Used, LRU)
- 维护一个有序单链表，当有新的数据被访问时，从链表头开始遍历链表：
- 若链表中存在新数据，将其删除，插入到链表头
- 若链表中不存在新数据：
- 若缓存未满，将新数据插入到链表头
- 若缓存已满，删除链表尾结点，将新数据插入到链表头
- 链表代码书写的注意事项：
- 警惕指针丢失和内存泄漏
- 插入节点时，注意操作顺序
- 删除链表结点时，手动释放内存空间
- 利用哨兵简化实现难度
- 针对链表的插入和删除操作，需要对插入第一个结点和删除最后一个节点的情况进行特殊处理
- 引入头结点，将head指针始终指向头结点，头结点指向第一个数据节点
- 边界条件处理
- 链表为空时
- 链表只包含一个节点时
- 链表只包含两个节点时
- 操作头结点和尾结点时
- 举例画图，辅助思考
- 警惕指针丢失和内存泄漏
- 5个常见的链表操作
- 单链表反转（分别使用迭代和递归实现）
- 链表中环的检测（迭代实现和快慢指针实现）
- 两个有序的链表合并（常规解法和递归解法）
- 删除链表倒数第n个结点（单指针两次遍历和双指针一次遍历）
- 求链表的中间节点（单指针两次遍历和双指针一次遍历）