常见的缓存策略：
1：先进先出FIFO（First In，First Out）
2：最少使用LFU（Least Frequently Used）
3：最近最少使用策略（LRU）
LRU可以使用 有序 单链表实现：其中越靠近尾部的节点是之前越早被访问到的。
当缓存中需要插入新数据
1：如果从头遍历链表，这个该数据已经存在，删除链表中的该数据，同时把该数据放在表头；
2：如果该数据不存在，则直接放在表头，如果链表已满则把尾节点删除；
链表与数组的区别：
链表有指针和节点的概念，通过指针指向节点，因此链表所占用的内存是不连续的；
单链表：
image.png
循环链表：（解决循环问题：约瑟夫环）
image.png
双向链表：
image.png
可以看出双向链表需要额外的两个空间来存储后续节点和前驱节点，
虽然比较浪费空间但可以支持双向遍历，更灵活；
如删除/插入 操作的两种类型：
1：删除/插入 等于某个值的节点；（一样）
2：删除/插入 给定指针指向的节点；（需要的时间复杂度(查询）：单链表的为O（n），双链表为O（1））
LinkedHashMap就是双链表的结构；
链表对于数组最大的好处：内存分配的灵活性；
（数组特性的要求连续内存 以及 ArrayList的自动扩容时损耗内存；）
网友评论