数组、链表、跳表

数组

时间复杂度

查找：O(1)

添加：O(n)，因为需要把插入位置后的元素都往后移动一个位置

删除：O(n)，因为需要把删除位置后的元素都往前移动一个位置

代码

// 基础
int a[100];
// java 在基础数组上封装了一层
ArrayList a = new ArrayList<Integer>;

链表

时间复杂度

查找：O(n)

添加：O(1)

删除：O(1)

代码

LinkedList 是一个双向链表

LinkedList linkedList = new LinkedList<Integer>();

跳表（只需要理解思想）

在链表的基础上升维，以空间换时间的方式，加速链表的查找时间复杂度

二维在原始链表递增一步，三维在二维上递增一步。。。

原始链表要 62 次才能查到的节点，跳表就只需要 10 次，跳表的查询时间复杂度为 O(log n)

Redis 上广泛应用跳表