在学习数据结构与算法的过程中,感觉真的是一入算法深似海,但是越学越觉得有趣。不过我们会发现在终身学习的过程中,我们都是越学越多,不知道的也越来越多,但是更渴望更多的知识,越是对知识感兴趣。
本期讲到了最常见的数据结构类型,分别有数组、链表、跳表。这一期我们一起来了解它们的原理与实现。
当今的高级数据语言中,对于数组里面的类型没有严格要求,相对来说比较多元化。 在语言下有一个标准的叫法叫做
泛型
,也就说任何一个单元类型都可以放入数组。
内存管理器
的;常数O(1)
;数组的问题关键是在增加与删除元素的时候。
假设现在我们定义了一个[A, B, C, E, F, G]
的数组,然后我们要插入一个D
到这个数组里面。现在假设我们要把D插入到指针3的位置,我们要怎么实现呢?
E
,F
,G
都挪动到各自的下一个指针;D
到指针3
上;具体的实现效果看下图:
因为插入操作的时候,我们需要挪动平均一半的元素(N/2),所以数组每次插入元素时,平均就是
O(n)
的时间复杂度。
删除元素也是同理的,假设我们现在有[A, B, C, Z, D, E, F]
的一个数组,我们现在需要把Z
从这个数组中移除。实现逻辑如下:
3
的值置空;D
、E
、F
三个值往上移动一个位置;Java
的数组语言中,我们需要把数组的长度减1即可;具体的实现效果看下图:
因为删除操作的时候,也是需要挪动平均一半的元素(
N/2
),所以数组每次删除元素时,平均就是O(n)
的时间复杂度。
操作类型 | 时间复杂度 |
---|---|
查询上一个 (prepend) | O(1) |
查询下一个 (append) | O(1) |
查询某一个元素 (lookup) | O(1) |
==新增结点 (insert)== | ==O(N)== |
==删除结点 (delete)== | ==O(N)== |
下来我们一起来看看另外一个数据结构链表
。链表的诞生就是为了解决数组的缺点。
链表的特性:
value
值与next
指针(指向下一个元素);Class
(类):一般都叫一个Node
;单链表
:只有一个next指针;双向链表
:拥有一个prev或者previous指针指向前一个元素;循环链表
:尾指针的next指针指向头指针;下来我们一起来看看一个链表新添加一个元素的原理:
next
指针指向新的Node;next
指针指向后一个元素;具体实现效果看下图:
链表的插入操作总共是2次,但是常数次的,所以时间复杂度为
O(1)
。
接下来我们一起来看看删除结点的原理,删除与新增大致上是一样的,是
next
,改为删除结点的下一个node;具体的实效效果看下图:
链表的删除操作只需要一次,所以时间复杂也是
O(1)
。
通过分析链表的新增和删除操作,我们发现链表中并没有像数组一样需要挪动一半或者多个的元素的位置和复制元素等。也是因为这样它的移动和修改操作的效率非常高为O(1)。但是在查询的时候,当我们需要访问链表中某一个值的时候,就相对变得复杂了,为O(N)。
我们来看看以下的链表时间复杂度:
操作类型 | 时间复杂度 |
---|---|
查询上一个 (prepend) | O(1) |
查询下一个 (append) | O(1) |
查询某一个元素 (lookup) | O(N) |
新增结点 (insert) | O(1) |
删除结点 (delete) | O(1) |
看完Array和Linked List的两种数据结构的特性后,我们可以发现是没有完美的数据结构的。如果有完美的那就不需要Array或者Linked List并存了。所以我们需要看场景来决定我们需要用那种数据结构。
后续有技术科学家对链表进行了优化,诞生出第三个数据结构叫做跳表(Skip List)。跳表可能有些小伙伴没有怎么接触过,但是其实它一直都在我们身边的应用中使用。在Redis里面就使用了跳表。不过面试过程中并不会给大家出跳表的题目来写程序,所以我们只需要理解它的原理即可。
跳表的核心是为了优化链表元素随机访问的时间复杂度过高的问题 (O(n)
)。
这个优化的中心思想其实是贯穿于整个算法数据结构,甚至也贯穿于整个数学与物理的世界。那就是
升维思想 / 空间换时间
- 顾名思义就是在原有的链表中添加第二维的链表叫第一级索引
。
我们看看下面图什么是一级索引:
假设现在我们需要访问结点7,添加了这个索引后,是怎么提高了访问速度呢?我们来看看下面的图:
虽然说速度是快了,但是能不能更快呢?可以的,只需要我们再叠加维度,用空间换时间的中心思想即可。
第二级索引比第一级的索引再走快一步,那就是每次走两步,也就是next+2。这样访问结点的时候就更快了。首先我们来看看加入第二级索引后的结构图:
加入了二级索引后,我们访问结点7的时候是怎么样的呢?
所以清晰看到,当我们升级多一层的维度后,链表的访问速度也会相对应的提升。也就是说,在一个非常长的链表中,我们可以加入N级索引,也就是提高N层的维度就可以提高这个链表访问的速度。总体来说我们就是需要添加
log2n
级索引,来达到最高级索引维度。
O(log n)
O(n)
;来源于覃超老师的PPT
O(log n)
;升维思想和空间换时间的思维,我们一定要记下来,并且融会贯通。后面在解决相应的面试题的时候我们会经常用到这种思维。比如:树,二叉搜索树等经常用高级数据库结构。
链表在日常工程中其实应用是很多的,但是因为这些都属于高级的数据结构了,无论是Java也好、C++、JavaScript还是Go语言,这些语言里面都提供了封装好的数据结构,我们只需要直接使用就可以了。
链表最常见的一个应用就是LRU Cache
,没有接触过的小伙伴,可以百度一下深挖一下。然后这里附上一道Leetcode
的题目[面试题 16.25. LRU缓存,这道题的话使用双链表就可以实现。有兴趣的小伙伴可以尝试实现。
跳表的话在Redis中就有应用到。想了解更多的小伙伴可以搜索Redis的跳跃表
进深挖。
O(1)
,但是删除与插入较慢 O(n)
;O(1)
,但是随机查询慢 O(n)
;O(log n)
,但是维护成本高;