数组

数组是线性数据结构的一种实现方式。当提到数组的时候,我可能会想到以下几个点:

  1. 顺序存储
  2. 连续的内存空间
  3. O(1)时间复杂度快速访问元素,O(N) 时间复杂度删除元素
  4. 固定大小
  5. 能更好的利用 CPU 的高速缓存机制(CPU 加载内存当中的内容至高速缓存会利用「就近原则」)
  6. 存储数据的类型必须相同

如何实现高效的随机访问

其中第三点提到的 O(1)时间复杂度访问元素,是数组这个数据结构特有的一个优势。之所以能达到这个效果,来自于第一点和第六点的两个限制。因为数组的元素说到底都是存储在内存中的,既然在内存中就会有地址来标识数据所处的位置。而数组中又限制只能存储相同数据类型的元素,所以我们很轻松的就可以通过一个公式计算出数组中某个元素的内存地址,进而直接通过这个地址去访问它。

element_address = base_address + data_type_size * i 计算第 i+1个元素的内存地址

在这里需要特别注意一点的是,数组高效的操作是「访问」而不是「查找」。万不可将两个操作混淆。访问包括计算内存地址+取值两个小操作。而查找则是需要通过一定的策略去遍历数组中的元素的。

为什么数组的「插入」和「删除」操作是低效的?

数组的插入操作大致可分为两种:

  1. 尾部
  2. 非尾部

其中从尾部插入元素的时间复杂度为 O(1),只需要一个简单的赋值操作即可,本质上来讲是一个「访问」操作的变种。而如果在数组头部和中间部分插入一个元素的话,可能就会涉及到一个非常昂贵的操作:「移动」。假设你要在数组第 k 个元素的位置插入一个新的元素,那边第 k 个元素至第 n(数组大小为 n)个元素就都需要向后移动一位,以便给新的元素让出位置。最坏的情况下,时间复杂度为 O(n)。

若读者仔细琢磨一下上面说的插入步骤,在结合文章最开始说的数组的第四个特点,我们就可以发现这里面还有一个隐含的风险:数组空间不够了怎么办?

如果出现了这种问题,肯定是需要从新开辟一块更大的内存空间,然后将所有的元素都 copy 过去。这样一来,时间复杂度妥妥的是 O(N),并且还增加了内存分配上的性能消耗。甚至是对内存空间也有一定的浪费。不过,对于这种昂贵的操作,很多编程语言都对其做了优化,比如设置一个更合适的数组内存空间分配策略,减少内存空间分配回收的次数等。

数组的删除操作基本上和插入操作面对的问题是一样的。虽然他不需要移动旧的元素给新的元素让出插入的位置,但是它要保证前面说到的数组的第一个特点:连续存储。所以,删除操作需要清除掉元素之间的「间隙」。不同之处在于,删除操作可以使用一些技巧来减少移动元素的次数:

对一个数组的元素执行了删除操作之后,先不移动元素,而是将此元素做一个标记。当数组的剩余空间已经没有的时候,可以统一对数组中的元素进行一次「整理」。

但是这个技巧的使用是有一个前提的:使用数组的人不需要数组「连续存储」的特性。

优点和缺点

优点

  1. 通过下标可以对元素进行快速随机访问,时间复杂度为 O(1)
  2. 可以更好的利用 CPU 的高速缓存

缺点

  1. 必须要一段连续的内存空间存储。若内存剩余容量够但是空间不连续,则为数组分配内存会失败
  2. 昂贵的「插入」和「删除」操作

链表

链表是按照一定的顺序通过指针将多个内存块串联起来的一种线性数据结构。当提到链表的时候,我通常会想到以下几个点:

  1. 对内存空间的连续性没有要求
  2. 变种很多:单链表,双向链表,循环链表,双向循环链表
  3. 操作复杂,尤其是对头结点,尾节点,甚至是空链表
  4. 无法做到快速的随机访问,只能从链表头部进行遍历。但是插入和删除操作的时间复杂度为 O(1)
  5. 没有固定大小,可以轻易的扩缩容

为什么链表的插入和删除操作可以达到 O(1)的时间复杂度?

其实,对于数组来说,它的插入和删除操作之所以昂贵,是因为数组的一个特性:连续存储。连续存储带来的好处就是可以通过公式计算出某个元素的内存地址,进而达到「随机访问」的效果。如果要保证这种「连续」的特性,那么是避免不了要频繁移动数组中的元素的。

链表都有哪些种类?

单链表

单链表是最简单的链表数据结构。它的每一节点通常由两个 field 构成:

  • value:存储该节点的数据值
  • ptr_next:存储下一个节点的内存地址

循环链表

循环链表和单链表唯一的区别就是在链表尾节点上。单链表尾节点 ptr_next 的值为 NULL,而循环链表为头结点的内存地址。通过将尾节点的 next 指针又指向了头结点,形成了一个环形的数据结构

双向链表

双向链表相较于单链表来说,其每一个节点不单单有后继指针,还有前驱指针。所以,双向链表可以实现两种相反方向的顺序访问。除了向使用者提供了另外一种访问链表的顺序之外,在特定场景下,他对于链表的删除和插入操作有一定的优化效果。

以删除来举例。如果我们想删除链表中的一个节点的时候,通常有两种方式可以对待删除节点进行描述:

  1. 删除内存地址为 P 的节点
  2. 删除值为 X 的节点

对于单链表来说,这两种方式没有任何区别。因为我们都需要从链表的头部开始遍历,直到找到待删除节点的前一个节点,再进行相应的操作。而对于双向链表来说,如果待删除节点是以内存地址来描述的话,我们就可以直接通过 p->ptr_pre 指针保存的内存地址定位到待删除节点的前一个节点。同理,对于插入操作来说也是一样的效果。

除了删除和插入操作之外,对于一个元素有序的链表而言。双向链表查询操作的效率也要高于单链表。因为双向列表通过记录上一次查找的位置,可以根据大小选择到底是查找前半部分还是后半部分的元素。

双向链表和单项链表的区别

很容易就可以看出,双向链表要比单项链表多出一个「前驱指针」,这意味着双向链表要消耗更多的内存空间。但是,消耗更多空间的同时也为特定场景下链表的插入,删除,查找等操作节省了一定的时间。这是一种典型的「以空间换时间」的思想。相反,在计算机世界中也有很多「以时间换空间」的例子:比如对于一些消耗内存较多的服务,我们可以限制它的内存配额,将部分数据存储在硬盘上。虽然读写硬盘可能会造成一定时间上的延迟,但是,「以时间换空间」的目的却达到了。

链表使用的注意事项

在编写关于链表相关的代码的时候,是非常容易出错的。尤其是在以下几个点上:

  1. 链表为空,是否可以工作
  2. 链表只有一个节点,是否可以工作
  3. 链表只有两个节点,是否可以工作
  4. 处理头结点和尾节点,是否可以工作

链表的常用操作

  • 单链表反转
  • 链表成环检测
  • 有序链表合并
  • 删除链表倒数第 N 个节点
  • 求链表的中间节点