数组

当你使用数组时，内存管理器会给你分配一段连续的空间。随机访问是O(1)的，插入删除慢。

链表

适合大量的增加和删除操作。增加和删除都是O(1)的，问题在于在哪删除。事实上你很多时候需要遍历链表，找到目标位置，再操作。

都因为Redis这个爹...... 跳表主要是为了弥补链表缺陷。链表的缺陷是查找是O(N)的

想要变快就需要空间换时间。考虑一个双向链表。我们如果有一个尾指针，则对尾部附近的元素进行查找可以是近乎O(1)的。如果在中心处再增加一个指针，则对中间位置的元素查找也是O(1)的。再不断细分下去......就变成了跳表。

alt

查找复杂度O(logN)，空间复杂度O(N)

LRU用了链表和HashMap 跳表哪里用不多说了吧？