正在学数据结构，学到链表这里，正在写一个稀疏矩阵的东西 创建一个用链表表示的稀疏矩阵的时候 书上方法：先设一个辅助数组，长度为读入矩阵最大可能维数（#define的），用来放头结点，让后读入非零元素的时候再一个个申请空间，插入链表。 网上搜的一个程序的办法：干脆先设一个长度很长的数组，头结点，非零元都放在里面。 我自己的想法。。所有节点都一个个申请空间，，， 我想知道的是：用链表的目的是什么？ 我以为是利用零碎空间：数组需要一大片连续空间，而链表是散落的，靠指针连着。而上面两个方法都预设了数组，这是为啥呢？那直接用数组不就好了吗？ 链表的目的是什么？？
这是一个典型的错误思考方向。
错误的根源在于，你把链表当成了一种整体的、不可分割不可更改的完整概念——然后，就着这个概念，考虑它的用途它的有点它的弱点，总结出一二三四然后背诵……完了。
完蛋。
这叫买椟还珠。
实际上，讲链表是为了给你引出“借助后向指针(next)组织数据”这么一个设计思路；同时借助这个思路完成一个典型的应用案例、学着分析它的空间/时间复杂度……
然后，马上领着你变换它、变形它、改进它……
比如，加上一个前向的prev指针，把单向链表改成双向链表；或者把next指针去掉、换成left/right指针，把它改成二叉树，等等。
这个过程中，真正想教给你的，是因地制宜的定制各种数据结构、分析其时空复杂度，为自己未来设计自己的算法/数据结构铺路。
因此，不要问“用链表的目的是什么”，而是反过来问：“链表是为了解决什么问题而发明的”、“有没有更优方案”、“如何找出更优方案”、“如何证明方案更优”……终至于“当我遇到某个没有先例的难题时，该如何优雅的解决它？”
当你这样问时，问题就很简单了。
1、链表是为了解决什么问题而发明的？
为了解决动态数量的数据存储。
比如说，我们要管理一堆票据，可能有一张，但也可能有一亿张。
怎么办呢？申请50G的大数组等着？万一用户只有一百张票据要处理呢？可申请少了又不够用啊……
而且，用数组的话，删除然后添加票据，是每次删除让后面五百万张往前移一格呢、还是每次添加从头搜索空闲格子？
那么，链表这种东西就是个很有效的数据结构，可以很有效的管理这类不定量的数据。
2、有没有更优方案？
有。
时间上，链表无法支持搜索，想找到特定数据只能遍历。
空间上，链表每个数据要额外占用一个指针的空间；对于int等基本数据类型，数据量暴增一倍（单链表）甚至两倍。
那么，为了在时间上优化它，我们可以搞成二叉树；然后通过先序/后序/中序遍历取得按一定规律排布的数据；也可以通过和根节点比较来快速确定数据在排序二叉树的左还是右子树上——这就得到了O(logN)的查询效率。
但这样空间占用就比单链表更多了。怎么办呢？
堆是一种优化到极致的二叉树；它实际上就是一个数组，左右节点对应的数组下标可以直接计算出来——这就省掉了指向子节点的指针。
不过，指针没了，灵活管理不定量数据、低消耗的插入删除等好处也没了。
一个折衷方案就是B树（以及B+树）——说白了，把节点做大一些，多存储一些数据，换句话说就是“让若干数据共用一组指针”，就把空间占用问题给解决了。
顺带的，这也避免了需要连续读取数据时不停的顺着指针跳转的问题，因此是一种非常适合磁盘存储的数据结构。
所以你说“用链表的目的是什么”？
没目的。
或者说，目的是让你学会因地制宜的、灵活的组织数据——而且随便你搞出多么奇怪的数据结构、多么复杂的数据组织形式，你都能清晰的给出它（对某个特定任务）的时间/空间复杂度。
当你能掌握到这个程度时，你完全可以把完全二叉树、满二叉树、红黑树、B树、B+树的定义统统忘掉；但只要有需要，你随时随地都能把你面对的数据整进一个结合了二叉树和队列优点的、不知道该叫什么的数据结构里——从而以最高效率完成你面对的任务。
换句话说，不要浮在表面、只看到链表二叉树之类东西；而是要深入进去，把它们统统拆散了、揉碎了、忘记了——你要做它们的发明者，不要做它们的使用者。
联系客服
