• Gist code

Hi! 1、缓存淘汰策略 常见的三中策略： 先进先出策略（FIFO） 最小使用策略（LFU） 最近最少使用策略（LRU）

2、链表 单链表

记录下一个结点地址的指针叫作后继指针next 头结点记录了链表的基地址 尾结点指向的不是下一个结点，而是指向一个空地址NULL。

链表的插入和删除操作是非常高效的，不需要搬移数据，时间复杂度是O(1)（仅仅说的是这个操作）。 链表随机访问第K个结点就没有数组高效，时间复杂度是O(n)。

循环链表 是一种特殊的单链表，与单链表的区别是单链表尾指针指向空结点NULL，循环链表的尾结点指针指向链表的头结点。 循环链表从链尾到链头比较方便。当处理的数据具有环型结构失特别适合采用循环链表。

双向链表 更加常用的链表。 每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。 需要额外的空间来存储后继结点和前驱结点的地址，但可以支持双向遍历。

优势： 插入和删除操作比链表更高效。 对于一个有序列表，双向列表按值查询效率也比单链表高一些。因为我们可以记录上次查找的位置P，每次查询时根据查找的大小决定往前还是往后，所以平均只需要查找一半的数据。

Java中，LinkedHashMap的实现原理就用到了双向链表的结构。

空间换时间思想 对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化，而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来减低内存的消耗。

双向循环链表

链表数组性能比较 数组和链表的对比不能局限于时间复杂度。 数据简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。链表在内存中不连续，所以对CPU并不友好，没办法有效预读。

数组的缺点就是大小固定，一经声明就要占用整块连续的内存空间。如果声明的数组过大，系统可能会没有足够连续的内存空间分配给它，导致内存不足。声明数组过小则可能出现不够用的情况。链表本身没有大小限制，天然的支持动态扩容，这是和数组最大的区别。

链表每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，内存消耗会加倍。 对链表频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片。

Gist code

To use, see:Jektify - Doc

jektify © 2019  +

Música

Jekyll plugin to generate html snippets for embedding Spotify Musics. To listen to the full song, open your Spotify and start these musics.

Goodbye!

---