数组、链表、跳表

Array（数组）

Array 增加、删除元素，需要挪动平均一半数组长度的元素，所以，对于 Array 来说，增删慢。但 Array 可以随意访问到任意元素，查询速度很快。

image.png

Linked List（链表）

Linked List 增加、删除元素，因为只需要改变 next 指针，增删不需要大量挪动链表中的元素
，所以，增删很快，但想找到一个元素必须从头结点或者尾结点一个一个的都查找一遍才能找到目标元素，查询速度就慢了。

Double Linked List 时间复杂度

image.png

Skip List（跳表）

为了解决链表查询速度慢的缺陷。

添加一级索引、二级索引、多级索引：

image.png

跳表时间复杂度为 O(logn) 。

image.png image.png

现实中因为链表元素的增删频繁变化，索引要随着每次的增删进行维护，所以，现实中的索引可能是不规整的，有的跳 2 步，有的可能跳 3 步。

image.png

跳表是在链表的基础上根据升维思想和空间换时间的手法，所以，跳表相对于链表的空间复杂度增加了，为 O(n)。

image.png

工程中的应用：

• LRU Cache - Linked list

• https://www.jianshu.com/p/b1ab4a170c3c

• Redis - Skip List

• https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html

参考链接：

• Java 源码分析（ArrayList）

• Linked List 的标准实现代码

• Linked List 示例代码

• Java 源码分析（LinkedList）

• LRU Cache - Linked list： LRU 缓存机制

• Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？