数组|链表|跳表的基本操作

• 数组：查找 O(1)，修改/插入 O(n)
• 链表：插入/修改O(1)，查找O(n)，它的结构是 Node { value: 值, next: 指针}
  • 增加操作: prevNode.next = targetNode; targetNode.next = nextNode;
  • 删除操作：prevNode.next = targetNode.next;
• 跳表：是链表的优化，主要在redis里面使用，理解数据结构即可。跳表查询的复杂度是log2(n) - 1 -> log(n)，但维护成本较高，增加和删除都需要更新它的索引。

思维

优化的思想核心是：升维，空间换时间。
比如给链表增加一个尾指针，双向查找，明显地缩短了查找的时间；再进一步，可以给链表加一个中指针，多向查找；再再进一步，可以给链表再加一些指针，比如中间的中间….等等，这个在redis里面就叫索引。

如何提高链表线性查找的效率？
添加索引，如果原始链表查找的速度是1，添加了一级索引之后速度就是1 * 2 = 2，以此类推。