内容概览

• 前言
• 数组
• 链表
• 跳表
• 实战题目解析
• 总结

前言

在 1. 复杂度分析（时间、空间复杂度）—— Ficow 陪你学算法和数据结构 中，Ficow 和您分享了自己的学习笔记。接下来，让我们开始学习具体的数据结构。

数组、链表是开发工作中使用最频繁的数据结构。跳表的使用频率略低，但是也值得我们去学习其原理以及设计思路。在本节中，主要会学到在构造算法时最常用的两种解决问题的方式：升维 和 空间换时间。

在开始阅读后文之前，我强烈建议您学习覃超老师在 极客时间 上开设的 算法训练营体验课，我已经亲身学习过并推荐给了朋友、同事们。

该课程的内容主要是以视频为主，质量非常高，而且短小精悍。主要涉及：

• 复杂度分析
• 数组、链表、跳表
• 树、二叉树、二叉搜索树
• 递归（代码模板非常给力）

截止 Ficow 创作此文当日，该课程售价还是 9.9 元，性价比还是挺高的。极客时间的新用户还可以免费领取，有效期是一周。赶快行动吧~

因为本文属于 Ficow 陪你入门 系列文章，所以 Ficow 也会记录自己的学习历程，并和您分享我自己的 学习笔记。欢迎您留言和我交流，大家共同进步！

数组(Array)

数组的特性：

• 在内存中开辟了一段连续的内存地址用于存储元素；
• 通过数组的下标访问任何一个元素的时间复杂度都为常数时间 O(1)，随机访问速度快；
• 插入/删除元素的操作，需要移动元素（甚至需要伸缩数组的长度），时间复杂度为 O(n)；感兴趣的朋友可以查看 Java ArrayList 中的 add, remove 函数的 源码

工程中的应用

Java ArrayList 源码分析

链表(Linked List)

链表的特性：

• 结点(node)通常被定义为引用类型(class)，每个结点包含了值和指向后一个结点的指针；
• 在内存中开辟了不连续的内存地址用于存储结点；
• 如果结点还包含指向前一个结点的指针，那么这就是一个双向链表；
• 如果链表的最后一个结点的 next 指针指向了头结点(链表的第一个结点)，那么这就是一个循环链表；
• 插入/删除结点的操作的时间复杂度：O(1)；查询结点的操作的时间复杂度：O(n)；

工程中的应用

Linked List 的标准实现代码
Linked List示例代码
Java LinkedList 源码分析

结点和节点的区别

在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。
在电信网络中，一个节点是一个连接点，表示一个再分发点或一个通信端点（一些终端设备）。

跳表(Skip List)

如果数组中的元素是有序的，我们可以使用二分查找来快速找到目标值；
同理，如果链表中的元素也是有序的，我们也可以利用分而治之的思想来加速查找操作。但是，链表不像数组那样拥有连续的内存地址，所以不太容易应用常规的二分查找算法。

跳表的特性：

• 跳表中的元素必须是有序的；
• 跳表对标的是平衡树和二分查找。插入、删除、搜索操作的时间复杂度都是 O(logn)。
• 原理简单、容易实现和扩展，效率更高。Redis、LevelDB等项目采用了跳表来替代平衡树。

跳表的实现过程

• 原始链表，查询操作的时间复杂度：O(n)。简单优化，增加头尾指针。

• 进一步优化，对一维的链表数据结构进行升维，升级到二维数据结构跳表。多一个维度，就有多一级的信息（以空间换时间），帮助我们加速原来在一维空间中的线性查找操作。
  

• 再进一步优化，添加二级索引以提高一级索引的查找效率。
  

• 最终，我们将建立多级索引。
  

• 跳表查询操作的时间复杂度分析，从原来的 O(n) 降到了 O(logn)。
  

请注意，由于增加、删除原始链表的结点等操作，实际的跳表结构可能并不会如此工整（严格的二分），有些索引可能会跨越很多或者很少的结点。

跳表的维护成本较高，增加、删除原始链表时，需要将索引都更新一遍。此时，在跳表中插入、删除结点的操作的时间复杂度不再是 O(1)，而是 O(logn)。

• 跳表的空间复杂度分析。
  

对上图中的值进行求和，最终的结果可以收敛到 n（不理解收敛的同学请去复习《高等数学》）。

工程中的应用

• LRU Cache - Linked List
  LRU缓存算法
  LeetCode - LRU 缓存机制
• Redis - Skip List
  跳跃表
  为啥 Redis 使用跳表(Skip List) 而不是使用 Red-Black?

实战题目解析

不得不提的就是覃超老师总结的练习步骤，可以帮助我们少浪费时间、少走弯路。毕竟，大多数人的学习都是从模仿开始的，学会了才会有进一步的创新。即使是数学家，也要先去学习前辈们总结出来的知识，然后才有能力去创造新的东西。

我个人非常认可这个练习步骤，感谢覃超老师：

覃超老师推荐的题目：

https://leetcode-cn.com/problems/container-with-most-water/
https://leetcode-cn.com/problems/move-zeroes/
https://leetcode-cn.com/problems/climbing-stairs/
https://leetcode-cn.com/problems/3sum/ (高频老题)
http://leetcode-cn.com/problems/lru-cache

练题的操作步骤：

• 写出自己的思路，多种解法都写下来，最后再去比较并找出最好的解法；
• 用代码实现自己的解法，然后用题目提供的测试数据进行测试（多尝试几组数据，比如特殊情况）；
• 测试通过后即可提交代码，然后查看该代码的审题结果，主要看耗时和时间复杂度；
• 寻求反馈：Code Review（尽量这样做）、查看题解（不要在糟糕的解法上浪费时间），理解优秀解法的思路还有代码的写法，然后自己参照着实践几遍；
• 复制题解的网址，删除域名中的 -cn，然后打开 LeetCode 国际站，在 题目的 Discuss 页面选择 Most Votes，消化吸收各种优秀的解法，同时提升英语水平。
• 把这个题目刷 5遍，5遍，5遍！！！千万不要只刷一遍！！！

总结

刷题必须付出足够的时间精力，学习、理解、练习、总结、再重复练习几遍、最终消化，然后就可以达到知行合一的水平。即使是面试官让你手写代码，你也不用再慌张~

推荐继续阅读：3. 树、二叉树、二叉搜索树 —— Ficow 陪你学算法和数据结构

参考内容：

极客时间
算法训练营体验课
LeetCode
LeetCode - 中文站
Java ArrayList 源码分析
Linked List 的标准实现代码
Linked List示例代码
Java LinkedList 源码分析
LRU缓存算法
LeetCode - LRU 缓存机制
跳跃表
为啥 Redis 使用跳表(Skip List) 而不是使用 Red-Black?