数据结构与算法4-链表(上)
链表(上)
经典的链表应用场景，就是LRU缓存淘汰算法
1.单链表
只要是链表，其插入和删除数据均为O(1)
2.循环链表
3.双向链表
注意：链表的插入、删除时间复杂度均为O(1)，这里双向链表的优点在于O(1)时间复杂度找前驱结点！O(1)时间复杂度找前驱结点！O(1)时间复杂度找前驱结点！
4.对双向链表的实际开发分析
5.双向循环链表
6.链表与数组性能比较
7.如何基于链表实现LRU缓存淘汰算法
8.如何利用数组实现LRU缓存淘汰策略
假设数组大一点，即缓存大一点，组头为旧进程，组尾为新进程。那么加入新缓存的话，在组尾插入 时间复杂度为O(1)。缓存未满的话，如果缓存中没有该进程则append，如果有该进程找搜索删掉再append；缓存满了的话，如果未有扩组再append，如果有已有，则搜索删掉再append。