数组与链表
线性表：就是数据排成像一条线一样的结构。数据最多只有前和后两个方向（数组、链表、队列、栈）
非线形表：数据之前并不是简单的前后关系。（二叉树、堆、图）
连续的内存空间和相同类型的数据，特性是“随机访问”。但是删除，插入非常低效，为了保证连续性，就需要做大量数据搬移工作。
数组 Array
数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
低效的插入和删除
插入 或 删除：
末尾插入，时间复杂度 O(1) ；开头插入，时间复杂度 O(n)；平均情况时间复杂度 (1+2+...+n)/n = O(n)
插入优化：
如果数据是无序的，不用管排序，那么，可以把插入位置 x 替换为新的值，再把旧值放入最后。
这样时间复杂度就会降到 O(1)
删除优化：
在不一定追求连续的时候，多次删除时，让他们集中删除。每次删除标记数据被删除，但不真正搬移数据，当数组没有更多空间，再一次性删除。
比如 JVM 标记清除垃圾回收算法的核心思想。
区别
链表：适合插入、删除，时间复杂度是 O(1)
数组：支持随机访问，根据下标随机访问的时间复杂度为 O(1)
链表 Linked List
时间复杂度
插入删除:
O(1)随机访问:
O(n)
空间复杂度
O(n)
跳表 Skip List
一种动态的数据结构
时间复杂度：
- 随机访问：
O(㏒n) - 插入删除：
O(1)
Redis 的有序集合是通过跳表来实现的：
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 按照区间查找
- 迭代输出有序序列