数组、链表和跳表的基本实现、特性
目录
数组
数组的实现在计算机中，底层的硬件实现的话会有一个内存管理器的东西，每当申请一个数组计算机会在内存之中开辟一段连续的地址，每一个地址就可以通过内存管理器进行访问。访问的时间复杂度O(1)，增加与删除，在java.util.ArrayList中的操作核心在于使用System.arraycopy()方法，例如：
显然如果在对你的数组有频繁的修改的时候，会出现大量想的复制操作。
链表
针对上面数组的缺点，使用链表改进。
在Java中java.util.LinkedList是标准的双向链表，在操作里面增加与删除操作，并不需要复制元素。查询操作时间复杂度O(n);
跳表（Skip List）
核心思想：升维思考，空间换时间
现实中跳表：因为里面的一些元素被增加与删除了。
增加和删除一个元素的话需要将，它的索引更新一遍，时间复杂度变成O(logn)。
补充阅读：
LRU缓存算法：https://www.jianshu.com/p/b1ab4a170c3c
跳跃表：https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.htm
为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？ https://www.zhihu.com/question/20202931
练习题