2. 数组、链表、跳表 —— Ficow 陪你学算法和数据结构

| 算法/数据结构

 

内容概览

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

 

前言

 

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(不理解收敛的同学请去复习《高等数学》)。

工程中的应用

 

实战题目解析

 

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

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

 

覃超老师推荐的题目:

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?

 

觉得不错?点个赞呗~

本文链接: 2. 数组、链表、跳表 —— Ficow 陪你学算法和数据结构

转载声明:本站文章如无特别说明,皆为原创。转载请注明:Ficow Shen's Blog

评论区(期待你的留言)