申请数组的时候，计算机在内存中开辟了连续的一段地址，每个地址通过内存管理器访问。
数组的增加和删除最好的情况是O(1)，只需要挪动一个元素。
最坏的情况是O(n)，有N个元素就需要挪动N个。
元素定义好之后，有所谓的value和next，next指向下一个元素的引用。
单向链表：只有一个next指针，就叫做单链表。
双向链表：往前指一个就叫做它的先前指针，叫做prev，或者是previous，叫做双向链表。头指针一般用head表示，尾指针一般用tail表示。
循环链表：如果最后一个元素的指针指回到head，就叫做循环链表。
链表增加节点，前继节点的next指向新节点，新元素的next指向之前的下一个节点。
链表删除节点：就是增加节点的逆操作，就是把前驱节点的next打掉，移到后继节点去。
| 方法 | 时间复杂度 |
|---|---|
| prepend | O(1) |
| append | O(1) |
| lookup | O(n) |
| insert | O(1) |
| delete | O(1) |
通过以上数据可以看到，链表在随机访问节点的时候，平均的时间复杂度是O(n)的。
| 方法 | 时间复杂度 |
|---|---|
| prepend | O(1) |
| append | O(1) |
| lookup | O(1) |
| insert | O(n) |
| delete | O(n) |
[1 2 3 4 5 6 7 8 9 10 ...]
提高查询效率——一级索引（“一级加速”）
[1 4 7 10 ...] # 一级索引
[1 2 3 4 5 6 7 8 9 10 ...]
进一步提高效率（“二级加速”）
[1 7 ..........] # 二级索引
[1 4 7 10 ...] # 一级索引
[1 2 3 4 5 6 7 8 9 10 ...]
有上千个节点，增加log2n个级索引。
[* * ] # 四级索引
[* * * ] # 三级索引
[* * * * * * * ] # 二级索引
[* * * * * * * * * * * * * * * ] # 一级索引
[*********************************************]
由于节点的增删改查，会导致索引不工整，维护成本相对较高。
在redis里面，就是使用的跳表。
原文：https://www.cnblogs.com/liuhuan086/p/13089363.html