链表和数组的区别
单链表
数组：连续的内存空间
链表：通过“指针”将一组零散的内存串联起来（单链表，双向链表，循环链表）
image.png
内存块称为链表的“结点”，为了把所有的节点串联起来，每个链表的结点除了存储数据，还会记录链上的下一个结点的地址，这个记录结点地址的指针叫 后继指针 next。
image.png
第一个结点叫头结点，最后一个是尾结点，尾结点指针指向空地址(这是为了防止尾结点的后继指针next 成为一个野指针，导致遍历链表停不下来，或者出现一堆本不属于该链表的垃圾数据等)
插入、删除
- 插入、删除一个结点，只要改变相邻的结点的指针就可以
- 插入、删除：在上一节点的后继指针指向新结点地址，新结点的后继指针指向下一个结点的地址
- 插入，删除结点时间复杂度 O(1)
- 删除某个结点的值等于某个给定值 时间复杂度为 O(n)
image.png
查询
- 访问第 K 个元素需要遍历
- 最好时间复杂度O(1)
- 最坏时间复杂度O(n)
- 平均时间复杂度O(n)
循环链表和双向链表
循环链表
- 循环链表是一种特殊的单链表，他的尾结点指针指向链表的头结点
- 使用场景适合具有环型结构的数据
image.png
双向链表
- 每个结点有两个指针，一个是前驱指针 prev 指向前面的结点，一个是后继指针 next 指向后面的结点
- 需要额外的两个空间来存储前驱结点和后继结点
- 支持双向遍历
- 浪费空间
- 插入，删除 O(1)
image.png
从链表中删除数据：
- 删除结点中“值等于某个给定值”的结点。 这种删除方法需要遍历整个链表，所以时间复杂度为O(n)
- 删除给定指针指向的结点 双向链表是O(1)，单链表是O(n)，单链表在删除给定指向指针的结点需要找到该结点的前置结点，但是前置结点需要遍历才能找到，遍历时间复杂度为O(n)
链表中删除数据：
- 和上面的操作相同
空间换时间
总结：
空间换时间：对于执行较慢的程序，通过消耗更多内存来优化
时间换空间：对于消耗内存过多的程序，通过消耗更多的时间来降低内存的消耗
双向循环链表
image.png
链表和数组性能对比
image.png
数组和链表的区别
- 数组优点：使用连续的内存空间，可以借助CPU的缓存机制，预读数组中的数组，访问效率较高
- 数组缺点：是大小固定，一经申明就要占用整块连续内存空间，如果声明数组过大，系统没有足够内存空间分配，会导致内存不足，如果声明内存过小，出现不够用，又要申请一个更大的内存空间，把愿数组拷贝过去，耗费时间
- 链表缺点：在内存中并不是连续存储，所以对CPU缓存不友好，没法有效预读
- 链表优点：没有大小限制，支持动态扩容
LRU
思路：
- 使用定长链表来保存所有缓存的值，并且最老的值放在链表最后面 当访问的值在链表中时： 将找到链表中值将其删除，并重新在链表头添加该值（保证链表中 数值的顺序是从新到旧） 当访问的值不在链表中时： 当链表已满：删除链表最后一个值，将要添加的值放在链表头 当链表未满：直接在链表头添加
image
