数据结构基础知识

跳表查询的时间复杂度分析

n/2、n/4、n/8、第k级索引节点的个数就是n/(2^k)

假设索引有h级，最高级的索引有2个节点。n/(2^h) = 2,从而求得h = log2(n) - 1

跳表:

原始链表大小为n，每2个结点抽1个，每层索引的节点数： n/2，n/4，n/8，…，8，4，2
原始链表大小为n，每3个结点抽1个，每层索引的节点数： n/3，n/9，n/27，…，9，3，1
空间复杂度是O(n)

跳表查询的时间复杂度分析
第k级索引
第k - 1 级索引

索引的高度：logn，每层索引遍历的节点个数：3
在跳表中查询任意数据的时间复杂度就是O(logn)

解决问题
升级维度
空间换时间

LRU最近最少使用
基于多链表来实现的。

可以通过HashMap + 双向链表实现。
HashMap保证通过key访问数据的时间为O(1)，
双向链表则按照访问时间的顺序一次穿过每个数据。
之所以选择双向链表而不是单链表，是为了可以从中间任意节点修改链表结构，而不必从头结点开始遍历。