从零开始学算法：6.链表与分块

在公众号中回复“ACM模板”你将免费获得我大学耗时四年整理的《ACM算法模板》。

一、背景

大家好，我是tiankonguse。
由于某些原因，经常有人想学习算法但之前又没有相关经验，不知道从何做起。
我思考了许久，计划写一个系列来分享如何入门学习算法。

之前已经分享了《认识算法》、《了解套路长啥样》、《排序算法》、《二分查找》、《万能数组》，这是第六篇《链表》。

一、基础知识

上篇文章《万能数组》在最后，遗留了一个问题：我们在中间删除或插入数据的时候，平均复杂度是O(n)。
另外，在空间用完重新分配时，也会有O(n)的调整时间，这些操作有时候不能接受。
于是我们就想，有没有更快的方法来插入或删除。
答案自然就是链表了。

使用数组之所以会面临插入或删除性能低的问题，就是因为数组的空间是定长连续的。
所以对应的解决方案自然就是非连续的数据结构了，最简单的就是链表。

二、单向链表

链表每个节点都包含两部分：数据、其他节点的位置信息。
对于位置信息一般使用地址指针标示，后面也会介绍其他的形式。

最常见的链表如下图，有一个数据和一个位置信息，我们称为单向链表。

我们使用这种方式，我们就再也不怕空间不够用了。
看下面的代码，可以发现，插入复杂度是O(1)的了，不过最后追增数据的复杂度是O(n)。
当然我们可以通过把最后一个节点储存起来，做到插入O(1)，这里我就不实现了。
不过这里有个问题就是插入或删除数据时，需要维护两个关系。

三、双向链表

上一小节的名字是单向链表，自然可以想到双向链表，也就是储存两个位置信息。

对于双向链表，有个好处是可以逆向遍历数据。
不过增加节点和删除节点的时候，需要维护四个关系。

四、循环链表

对于单向链表，我们可以发现链表的尾部的位置信息浪费了。
对于双向链表，则是表头的ptr信息和表尾的next信息浪费了。
如果我们利用起来的话，表尾指向表头，表头指向表尾，那就是循环列表了。

对于循环列表，我们就可以直接得到表尾，然后快速从队尾插入数据。

五、下标链表

第一小节提到过，链表的每个节点都包含两部分：数据、其他节点的位置信息。
而对于位置信息，我们其实可以不使用指针的，在ACM中我们都是使用数组下标来标识的。

具体来看，就是预先生成一个节点数组，然后用数组的下标代表节点的指针。
这样有个好处，以操作数组的形式才做链表。

六、块状链表

对于链表，虽然在中间插入删除有天然优势，那自然也有对应的弱势。
聊表下标定位效率低下，需要从链表头部一个一个的循环才能找到指定下标的节点。

五六年前，在大学ACM比赛的时候，经常使用一种折中的方法，就是块状链表。
这个算是结合了数组和链表，然后操作复杂度也可以接受。

具体分析，数组是连续的内存，所以可以O(1)定位，但是插入删除是O(n)。
链表是非连续内存，所以可以O(1)插入和删除，但是定位要O(n)。
算是两种性质相反的数据结构，结合之和可以做到O(sqrt(n))的复杂度。
而ACM比赛的时候，数据往往是十万百万级别，开放一下不过几百几千，也就变得可以接受了。

具体实现也很简单，就是把数组当做数据节点，然后使用指针连起来就行了。

实际操作中，只需要维护数组节点当前使用数据的个数以及下个数组节点的位置即可。
在插入数据时，需要判断数据的个数是否超过数组大小，超过了就需要分裂成两个数组节点。
在删除数时，可以判断一下当前数组和下个数组的总个数是否小于指定值，小于了就合并。
下标定位的时候，每次可以跳过一个数组，所以速度就加快了。

查找时循环数组找到节点，然后使用下标具体定位数组即可。

插入的时候，先找到对应的数组节点。
如果数组节点恰好满了，需要拆分为两个，数据分两半，然后确定应该插入到那个数组。
然后使用插入逻辑插入到具体的数组里（整体后移）。

删除就简单了，直接先删除，然后判断是否需要合并，需要就合并。

分块链表的实际场景很多，如文本编辑器、双向队列（申请新内存时，不需要copy全量数据）等。

七、最后

这篇文章介绍了单向链表、双向链表、循环链表，下标储存时链表、分块链表，几乎覆盖了所有的链表数据结构。
对于普通的序列，我们使用分块链表来优化了，实现方式的成本与时间复杂度O(sqrt(n))都可以接受了。
而对于有序的序列，我们有另一种优化方式，复杂度可以优化到O(log(n))，下篇文章分享给大家。

注：如果可以随手快速敲出一个平衡树，或者变种平衡树，这些其实小众的数据结构其实都不需要了。

本文首发于公众号：天空的代码世界，微信号：tiankonguse-code。