用链表的目的是什么？省空间还是省时间？ 第1页

这是一个典型的错误思考方向。

错误的根源在于，你把链表当成了一种整体的、不可分割不可更改的完整概念——然后，就着这个概念，考虑它的用途它的优点它的弱点，总结出一二三四然后背诵……完了。

完蛋。

这叫买椟还珠。

实际上，讲链表是为了给你引出“借助后向指针(next)组织数据”这么一个设计思路；同时借助这个思路完成一个典型的应用案例、学着分析它的空间/时间复杂度……

然后，马上领着你变换它、变形它、改进它……

比如，加上一个前向的prev指针，把单向链表改成双向链表；或者把next指针去掉、换成left/right指针，把它改成二叉树，等等。

这个过程中，真正想教给你的，是因地制宜的定制各种数据结构、分析其时空复杂度，为自己未来设计自己的算法/数据结构铺路。

因此，不要问“用链表的目的是什么”，而是反过来问：“链表是为了解决什么问题而发明的”、“有没有更优方案”、“如何找出更优方案”、“如何证明方案更优”……终至于“当我遇到某个没有先例的难题时，该如何优雅的解决它？”

当你这样问时，问题就很简单了。

1、链表是为了解决什么问题而发明的？

为了解决动态数量的数据存储。

比如说，我们要管理一堆票据，可能有一张，但也可能有一亿张。

怎么办呢？申请50G的大数组等着？万一用户只有一百张票据要处理呢？内存小于64G拒绝运行？可申请少了又不够用啊……

而且，用数组的话，删除然后添加票据，是每次删除让后面五百万张往前移一格呢、还是每次添加从头搜索空闲格子？如何区分空闲格子和值为0的数据？搞区分的话是多占用空间呢还是占用数据值域？占用了值域会不会使得数据处理变得格外复杂？会不会一不小心就和正常数据混淆？万一拿来区分的字段在某个版本后废弃不用、或者扩充值域了呢？

你看，满是棘手的问题。

那么，链表这种东西就是个很有效的数据结构，可以很有效的管理这类不定量的数据。

2、有没有更优方案？

有。

时间上，链表无法支持搜索，想找到特定数据只能遍历。

空间上，链表每个数据要额外占用一个指针的空间；对于int等基本数据类型，数据量暴增一倍（单链表）甚至两倍。

那么，为了在时间上优化它，我们可以搞成二叉树；然后通过先序/后序/中序遍历取得按一定规律排布的数据；也可以通过和根节点比较来快速确定数据在排序二叉树的左还是右子树上——这就得到了O(logN)的查询效率。

但“随随便便插入数据”的二叉树很可能“偏”的非常厉害；极端情况下就退化成了空间消耗更高但效率没有丝毫提升的链表（绝大多数的左或右指针空着）。因此我们需要研究怎么样的二叉树才能有最好的查询效率、怎样才能保持二叉树的良好性能——于是就有了满二叉树、平衡树、红黑树等概念/算法。

但这样空间占用就比单链表更多了。怎么办呢？

堆是一种优化到极致的二叉树；它实际上就是一个数组，左右节点对应的数组下标可以直接计算出来——这就省掉了指向子节点的指针。

不过，指针没了，灵活管理不定量数据、低消耗的插入删除等好处也没了。

灵活管理不定量数据这个需求容易满足：我们把数组分成若干段、然后调整一下计算出来的下标就行了。

比如，数组1一共256个元素，用满后不得不又申请了一个1024元素的数组2；那么对于下标1000，我们就不能访问数组1下标1000的元素，而应该去数组2查找；并且在数组2中，它的下标应该是1000-256——你看，一旦内部做了这样一个自动调整，我们就又把“按需申请空间”能力找回来了。

只不过，这个方案里，插入/删除会变得特别麻烦——堆排序本身已经够烧脑了，结果算出来的下标还要根据配置截成很多段、还要在每段里重新计算……

即便这个算法我们可以轻易hold住，但每次插入/删除造成海量元素位置移动，这个消耗也太可怕了——O(N)的消耗！

另一个折衷方案就是B树（以及B+树）——说白了，把节点做大一些，多存储一些数据，换句话说就是“让若干数据共用一组指针”、或者说是一种“半堆半树/堆树结合”的数据结构：用更少的指针得到差不多的性能，这就把空间占用问题和高消耗的插入删除问题给解决了，同时查找效率仍然保持在O(log N)。

顺带的，这也避免了需要连续读取数据时不停的顺着指针跳转的问题，因此是一种非常适合磁盘存储的数据结构。

所以你说“用链表的目的是什么”？

没目的。

或者说，目的是让你学会因地制宜的、灵活的组织数据——而且随便你搞出多么奇怪的数据结构、多么复杂的数据组织形式，你都能清晰的给出它（对某个特定任务）的时间/空间复杂度。

当你能掌握到这个程度时，你完全可以把完全二叉树、满二叉树、红黑树、B树、B+树的定义统统忘掉；但只要有需要，你随时随地都能把你面对的数据整进一个结合了二叉树和队列优点的、不知道该叫什么的数据结构里——从而以最高效率完成你面对的任务。

换句话说，不要浮在表面、只看到链表二叉树之类东西；而是要深入进去，把它们统统拆散了、揉碎了、忘记了——你要做它们的发明者，不要做它们的使用者。

你要学的，是最高效率把玩海量数据的思路；你不仅要能因地制宜的给出解决方案、还要有能力给出综合最优的方案（并作出证明）——停留在链表这个表面上，那是连门在哪都没摸到，谈何入门。

拿程序设计语言的术语来说，链表的定义并不是final class List<T>，而是abstract class List<T>——前者是“这是一个现成的完美品”“用就对了别管它怎么实现也别试图改进它”；后者是“这并不是一个完美的现成品”“你必须彻底搞明白它的设计思路”“你必须自己改进它”……

可以说，本科的算法与数据结构这本书，其中一大半的篇幅都在教这个改进过程/思路——只不过绝大多数的师生乃至写教材的老师都没意识到这点，反而习惯性的分章节摘开、把明显具有演进关系的概念割裂成一个个final class讲解/学习，再加上考试指挥棒的作用，这才使得绝大多数人被误导到了错误的方向。

数组可以提供O(1)的随机访问，链表可以提供O(1)的插入和删除操作。

数组更紧凑，一般认为更省空间，数组中相邻的元素在物理内存上也是相邻的，所以读取相邻或者附近数组元素时时更容易命中cache（这个一般是说cpu中的cache）。而链表则更灵活，我们往往会在链表的头部或者尾部进行增删的操作，如果我们需要在链表中间进行插入或者删除，我们往往会结合其他的数据结构，比如说用hash表做个索引，来实现元素查找的快速定位。

但对于问题中所描述的稀疏矩阵，如果使用二维数组，这个空间浪费就比较严重了，我们可以使用链表来保存所有非零元，每一个非零元为一个链表元素，再用一个数组或者hash表来存储链表头，这样的话，如果矩阵非常稀疏，那的确是节省空间的。可这样这个数组随机访问就比较费劲了。

其实如果我们要描述一个稀疏矩阵，简单点，我们就定义一个二元组 （（x,y）-> value）的集合, 这个集合的实现可以是数组，可以是链表，也可以两者结合，可以是哈希表，可以是任何数据结构。这取决于你要如何访问你的数据，你是要随机访问还是连续访问，你是需要增删操作为主，还是读取操作为主，你是更看重读写消耗的时间，还是更看重空间的使用率，还是两者要结合。这个没有固定的做法，书上的做法也就是个例子，实际中还是具体情况具体分析的。