day04 链表

1、缓存的淘汰策略？

• 先进先出策略FIFO（First In, First Out）

• 最小使用策略LFU （Least Frequently Used）

• 最近最少使用原则LRU （Least Recently Used）

2、链表与数组的区别？

1、数组需要一段连续的内存空间来存储；链表则可以使用零散的内存块，通过指针串联起来使用。

1. 单向链表

2. 双向链表

3. 循环链表

4. 双向循环链表

   
   单向链表.png

循环链表.png 双向链表.png 双向循环链表.png

3、链表的时间复杂度？

单向链表的插入和删除仅需要更改指针的位置即可，故插入和删除的时间复杂度为O（1）,但是它的随机访问就比较低效了。需要从头开始按照指针来找，随机访问的时间复杂度为O（n）

4、时间换空间、空间换时间的设计思路

• 内存充足，要求代码执行速度快，空间换时间

• 内存紧缺，时间换空间

5、如何手写实现链表实现？

1. 决心 + 付出精力

2. 理解指针或引用的含义：指针存储了变量的内存地址

3. 警惕指针丢失和内存泄漏

4. 利用哨兵简化实现难度（对第一节点和最后一个节点做特殊处理。即哨兵解决边界问题）：带头链表

   img

5. 重点留意边界条件问题

6. 举例画图，辅助思考

7. 多些多练，没有捷径