01. 数组&链表

01. 数组 Array

• Java/C++ -> int a[100];
• Python -> list = []
• JS -> let x = [1, 2, 3]

  1.1 数组的查询

数组是内存中一段连续的存储单元，可以根据下标随机访问数组中的任意元素。时间复杂度为。

1.2 数组的插入和删除操作

• 为了保证数组元素是连续的，那么在插入元素D的时候，需要将5，4，3所在的元素依次往后移动一个元素的位置，给D留出能够插入的位置。所以该时间复杂度为；
• 但是如果刚好要在数组的末尾插入元素的时候，那么就不需要挪动任何元素，直接进行插入操作就好，该时间复杂度为。删除操作同理。

  1.3 总结

1. 查询操作：
2. 插入操作： 【平均情况】；【最好情况】
3. 删除操作： 【平均情况】；【最好情况】

4. 头尾结点增加删除：
   

   02. 链表

   为了改善插入和删除操作，让其变得更快，这就引出了链表：

5. 单链表

6. 双链表

2.1 单链表(Linked List)

本质上就是一个个元素用 指针 相连，指针链向其后继节点，用 next 表示。

• 单链表的变体：

这种单链表的好处是：提供了头指针和尾指针，很清楚的知道单链表的头和尾在哪。

2.2 链表的插入和删除

• 链表插入

将新节点的 next 指针指向要插入的位置元素，然后将前面的元素的 next 指针指向新节点。

• 链表的删除

将要删除元素前面元素的 next 指针指向要删除位置上后面的元素，然后将要删除的元素节点在内存中释放掉。

综上，链表的删除和添加元素的时间复杂度为。性能要优于数组的插入删除操作。但是链表的查找的时间复杂度是

2.3 双链表(Doubly Linked List)

双链表不同于单链表，其既有前驱又有后继。这样在查询链表元素会更加方便快捷一点。

2.4. LinkList各种操作时间复杂度

03. 跳表（Skip List）

在Redis中经常使用，面试中不会经常出题，所以以理解其工作原理为主

LinkList由于其随机访问的时间复杂度为O(N)，由于链表是简单的线性结构，一维的结构。所以访问某一元素的时候，必须从头开始遍历。
如何给链表加速？？

• 升维思想：空间换时间
• 

• 添加尾指针之后，对于处于链表后面元素的访问会变快。那么可不可以在链表中间多增加几个指针，那么访问中间的元素时间复杂度也会快很多。基于这种思想，跳表出现。

  3.1 添加一级索引

  
  原始链表的结点始终指向next；而索引指向的是next+1(2*next)；索引比原始链表的速度快2倍，每次跨2个元素。

  3.2 添加二级索引

  
  二级索引在一级索引的基础上，又要快两倍，是原始链表的4倍，每次跨4个元素。

  3.3 多级索引

  如果现实情况下，链表很长，还可以添加多级索引。
  
  增加 个索引

  3.4 跳表查询的时间复杂度分析

  n/2、n/4、n/8、第 k 级索引结点的个数就是 n/(2^k)
  假设索引有 h 级，最高级的索引有 2 个结点。n/(2^h) = 2，从而求得 h = log2(n)-1
  

• 索引的高度：，每层索引遍历的结点个数：3

• 在跳表中查询任意数据的时间复杂度就是

  3.5 现实中跳表形态

  
  维护成本较高，结点变化后，会导致索引更新

  3.6 跳表的空间复杂度分析

  

04. 工程应用

• LRU Cache - Linked list
  • https://www.jianshu.com/p/b1ab4a170c3c
  • https://leetcode-cn.com/problems/lru-cache

• Redis - Skip List

  • https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
  • https://www.zhihu.com/question/20202931

    05. 小结

• 数组、链表、跳表的原理和实现

• 三者的时间复杂度、空间复杂度
• 工程运用

• 跳表：升维思想 + 空间换时间

  06. 参考链接

• Java 源码分析（ArrayList）

• Linked List 的标准实现代码
• Linked List 示例代码
• Java 源码分析（LinkedList）：双向链表结构
• LRU Cache - Linked list： LRU 缓存机制
• Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？

07. 练习

7.1 实战练习题目 - Array

1. https://leetcode-cn.com/problems/container-with-most-water/
2. https://leetcode-cn.com/problems/move-zeroes/
3. https://leetcode-cn.com/problems/climbing-stairs/

4. https://leetcode-cn.com/problems/3sum/ (高频老题）
   

   7.2 实战练习题目 - Linked List

5. https://leetcode-cn.com/problems/reverse-linked-list/

6. https://leetcode-cn.com/problems/swap-nodes-in-pairs
7. https://leetcode-cn.com/problems/linked-list-cycle
8. https://leetcode-cn.com/problems/linked-list-cycle-ii

9. https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
   

   7.3 homework

10. https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

11. https://leetcode-cn.com/problems/rotate-array/
12. https://leetcode-cn.com/problems/merge-two-sorted-lists/
13. https://leetcode-cn.com/problems/merge-sorted-array/
14. https://leetcode-cn.com/problems/two-sum/
15. https://leetcode-cn.com/problems/move-zeroes/
16. https://leetcode-cn.com/problems/plus-one/