空间换时间&时间换空间
空间换时间的设计思想：当内存空间充足的时候，为了追求代码更快的执行速度，就可以选择空间复杂度相对较高、使时间复杂度相对很低的算法或者数据结构。
时间换空间的设计思想：内存空间比较紧缺时，可以选择空间复杂度相对较低，但时间复杂度相对很高的算法或者数据结构，来节省内存空间。
缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果通过缓存技术，事先将数据加载到内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。
对于执行较慢的程序，可以通过消耗更多的内存来进行优化；
对于内存消耗过多的程序，可以通过消耗更多的时间来降低内存的消耗。
链表的存储结构
数组需要一块连续的内存空间来存储，需要事先申请需要的内存空间；而链表通过"指针"将一组零散的内存块串联起来使用，不会占用还未使用的内存空间。
三种最常见的链表结构
单链表
链表通过指针将一组零散的内存块串联在一起，内存块称为链表的“结点”。每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，叫做后继指针next。
上图中有两个特殊的结点，分别是第一个结点（头结点）和最后一个结点（尾节点）。
头结点用来记录链表的基地址，用它可以遍历得到整条链表。
尾结点指向一个空地址NULL，表示这是链表上最后一个结点。
循环链表
循环链表跟单链表的区别在尾结点指针是指向链表的头结点。
和单链表相比，循环链表的有点是从链尾到链头比较方便。
当要处理的数据具有环形结构特点时，采用循环链表实现代码会简洁很多。
双向链表
双向链表支持两个方向，每个结点同时有后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址，存储同样的数据，双向链表要比单链表占用更多的内存空间。有点是双向链表可以支持O(1)时间复杂度的情况下找到前驱结点。
java中的LinkedHashMap就用到了双向链表这种数据结构。
双向循环链表
三种基本操作
删除操作
从链表中删除一个数据有两种情况：
- 删除结点中“值等于某个给定值”的结点
- 删除给定指针指向的结点
对于第一种情况，各种链表都需要从头开始遍历对比，直到找到值等于给定值的结点，然后再删除。
单纯的删除操作时间复杂度是O(1)，但遍历查找的时间复杂度是O(n)。链表操作的总时间复杂度为O(n)。
对于第二种情况，删除某个结点q需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，单链表还是要从头开始遍历链表，直到p->next=q，说明p是q的前驱结点。
双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。
所以，单链表删除操作的需要O(n)的时间复杂度，而双向链表需要O(1)的时间复杂度。
插入操作
如果希望在链表的某个结点前面插入一个结点，双向链表需要O(1)的时间复杂度；
单向链表需要O(n)的时间复杂度，因为单链表都需要从头结点开始遍历，直到找到前驱结点。
查询操作
链表的随机访问第k个元素，必须根据指针一个结点一个结点地依次遍历，直到找到相应的结点。链表随机访问需要O(n)的时间复杂度。
对于一个有序链表，双向链表的按值查询的效率会比单链表高一点。记录上次查找的位置p，每次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，双向链表平均只需要查找一半的数据。
链表VS数组性能大比拼
数据和链表的时间复杂度：
时间复杂度 数组 链表
插入删除 O(n) O(1)
随机访问 O(1) O(n)
数组简单易用，在实现上是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储的，所以对CPU缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小限制，天然地支持动态扩容。
java中的ArrayList容器的动态扩容，存在数据拷贝的操作，而数据拷贝的操作是非常耗时的。举一个稍微极端的例子。如果我们用ArrayList存储了1GB大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList会申请一个1.5GB大小的存储空间，并且把原来那1GB的数据拷贝到新生请的空间上。
如果对内存的使用非常苛刻数据就更适合，因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。
对链表进行频繁的插入、删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，对于java语言，就有可能导致频繁的GC(Garbage Collection，垃圾回收)。
LUR缓存
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
常见的缓存淘汰策略
- 先进先出策略FIFO（First In，First Out）
- 最少使用策略LFU（Least Frequently Used）
- 最近最少使用策略LRU（Least Recently Used）
假如你买了很多本技术书，但有一天发现，这些书太多了，太占书房空间了，你要做个大扫除。那这个时候，扔掉一些书籍。你会选择扔掉那些书呢？
LRU缓存的实现
思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表：
1.如果此数据之前已经被缓存链表了，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2.如果此数据没有在缓存链表中，则将此结点插入到链表的头部。
如果此时缓存超过容量，则链表尾结点删除。
class ListNode(ohject):
def __init__(self, val, n = None):
self.val = val
self.next = n
class LRUCache:
"""
一个LRU缓存
维护了一个有序单链表，越靠近链表尾部的结点是越早之前访问的
"""
def __init__(self, capacity,: int = 10):
self.cap = capacity
# 哨兵结点，本身不存储任何数据
self.head = ListNode(Node, Node)
self.length = 0
def __len__(self):
return self.length
def get(self, val: object) -> bool:
"""获取指定缓存数据
思路：从链表头开始顺序遍历
1.如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入链表的头部
2.如果此数据没有在缓存链表中，则将新的数据结点插入链表的头部
- 如果此时缓存已超过容量，则将链表尾结点删除
"""
不管缓存有没有满，访问都需要遍历一遍链表，时间复杂度为O(n)。
也可以用数组实现LRU缓存淘汰策略：
class LRUCache:
"""
通过数组array实现的简易LRU缓存
维护一个list，越靠近尾部表示是越早之前访问的。
"""
def __init__(self, capacity: int = 10):
self.cap = capacity
self._data = [] # 存储数据
def __len__(self):
return len(self._data)
def __str__(self):
return str(self._data)
def get(self, val: object) -> bool:
"""
获取指定缓存数据
参数：
val：要获取的数据
返回：
存在于缓存中，返回True，否则返回False
"""
for i in range(len(self._data)):
if self._data[i] == val:
self._data.insert(0, self._data.pop(i))
return True
# 如果此数据没有缓存在链表中
self._data.insert(0, val)
# 添加数据导致超过容量则要删除尾结点
if len(self) > self.cap:
self._data.pop(len(self) - 1)
return False
网友评论