用链表的目的是什么？省空间还是省时间？
咱们先别急着给它贴标签，先看看链表到底是个啥。你可以把它想象成一串用线连起来的珠子，每颗珠子（节点）里面不仅装着你的数据，还装着下一颗珠子的“地址”，就像一个指示牌，告诉你下一位在哪里。最后一颗珠子呢，它的指示牌就指向“空”，表示旅程结束了。
链表的“省空间”：灵活的身躯
首先，聊聊链表为啥能“省空间”。这里的“省空间”，主要是指它相比于数组这类连续存储的数据结构，在某些情况下更有效率。
你想啊，数组就像一栋楼，每个房间（元素）的大小固定，而且紧挨着。你想往里面放东西，就得先确定好楼有多大，每个房间放多少东西。一旦房间定下来了，中间想插个房间，或者想拆掉一个房间，那就麻烦了，可能得重新规划整个楼的结构，甚至得搬家。
链表就不一样了。它更像是一条条独立的船，每条船（节点）可以停靠在任何地方，但船上都系着一根绳子，绳子的另一头连着下一条船。你想在船A和船B之间加一条船C，很简单，你只需要把船A的绳子接到船C，再把船C的绳子接到船B就行了。原有的船A和船B都没动地方，只是调整了一下连接。
这种动态分配存储空间的特性，在很多场景下就显得非常“省空间”。
内存利用率高，避免浪费： 想象一下，你要创建一个能存储 1000 个用户的列表。如果用数组，即便你现在只有 10 个用户，你也得预留 1000 个位置的内存，剩下的 990 个位置就空在那儿，白白占用了内存。而链表，你一开始只需要为这 10 个用户创建 10 个节点，内存占用很少。当用户增长到 500 个时，你再创建 490 个节点，内存是按需增长的。这种按需分配、动态扩容的特性，避免了预留大量未使用空间的浪费，特别是在数据量不确定或者经常变动的情况下。
插入和删除操作的高效性： 还是以数组为例，如果想在数组的中间插入一个元素，你需要将插入点后面的所有元素往后移动一位，这会消耗很多时间（尤其当插入点靠前，数据量大的时候）。删除也是一样，需要将删除点后面的元素往前移动。链表呢？就像前面说的，你只需要修改一两个节点的指针（连接线）就行了。插入一个节点，只需要找到插入点的前驱节点，修改它的指针指向新节点，再把新节点的指针指向原有的后继节点。删除一个节点，只需要修改它前驱节点的指针，让它直接指向被删除节点的后继节点。这种O(1)时间复杂度的插入和删除（前提是你知道要插入或删除的位置），在需要频繁修改数据顺序的场景下，是极其省时间的，间接也避免了因反复移动数据而产生的潜在内存碎片问题，从而也算是一种“省空间”的优化。
链表的“省时间”：灵活的调度
如果说空间是“量”，那么时间就是“速”。链表在某些“时间”消耗上也表现出色。
频繁插入/删除： 刚才也提到了，在链表的任何位置插入或删除元素，理论上只需要修改少量指针，时间复杂度是O(1)。如果数据结构是数组，插入/删除中间元素就需要移动大量数据，时间复杂度是O(n)。所以，如果你的应用需要频繁地在列表的中间添加或移除数据（比如实现一个待办事项列表，经常需要插入新的任务或者删除已完成的任务），链表会比数组快得多。
动态内存管理： 链表的数据节点可以分散存储在内存的任意位置，它们之间通过指针连接。这意味着在内存分配上，它比需要连续内存空间的数组更灵活。数组在内存中需要一块连续的区域，如果内存不够连续，就无法分配，即使总内存是足够的。而链表只需要为每个节点找到一块小的、可用的内存空间即可，这在内存碎片化的环境中，会更容易分配成功，也算是一种“省时间”的策略，避免了因内存不连续而进行的繁琐的内存整理或分配失败。
但别忘了，链表也有它的“代价”
当然，链表不是万能的，它也有它的“缺点”，这些缺点反过来也会影响“空间”和“时间”的效率。
访问速度慢（O(n)）： 链表不能像数组那样通过一个简单的索引（比如`arr[5]`）直接定位到第 5 个元素。你想找到链表中的第 5 个节点，你只能从头节点开始，一个一个地跟着指针往下找，直到找到第 5 个。这个过程的时间复杂度是O(n)，也就是你想要找的元素越靠后，花费的时间就越多。如果你需要频繁地随机访问数据，链表就会非常低效。数组的随机访问是O(1)，这是它的巨大优势。
额外的空间开销（指针）： 每个链表节点除了存储你的数据，还需要一个额外的指针（或两个，如果是双向链表）来指向下一个（或前一个）节点。当你的数据本身很小（比如只是一些布尔值或单个字节的字符），而指针的大小相对较大时，这些指针所占用的空间就会成为一个不小的开销。想象一下，你有 1000 个节点，每个节点除了数据，还有一个 8 字节的指针，那么你就额外用了 8000 字节的内存来存储这些指针，而这些空间并没有直接存储你的“有意义”的数据。
所以，链表究竟是省空间还是省时间？
答案是：取决于具体的使用场景和需求，链表在某些方面“省”了空间（避免浪费，动态分配），在某些方面“省”了时间（频繁插入删除），但也为另一些方面（随机访问）付出了“时间”和“空间”的代价（指针开销）。
如果你需要频繁地在数据中间进行插入和删除操作，而且不经常需要随机访问数据，那么链表会是一个非常高效的选择，它在“时间”和“空间”的灵活性上表现出色。
如果你需要频繁地随机访问数据，或者数据量固定且不需要频繁修改，那么数组或者其他更适合的结构（比如动态数组ArrayList、Vector）会是更好的选择，它们在访问速度上具有天然优势。
总而言之，链表是一个非常重要的、提供了另一种视角来组织和管理数据的工具。理解它的工作原理和权衡，才能在实际编程中做出最明智的选择。它不是一个普适的“最快”或“最省”的答案，而是一个在特定场景下能发挥巨大作用的解决方案。
网友意见
这是一个典型的错误思考方向。
错误的根源在于，你把链表当成了一种整体的、不可分割不可更改的完整概念——然后，就着这个概念，考虑它的用途它的优点它的弱点，总结出一二三四然后背诵……完了。
完蛋。
这叫买椟还珠。
实际上，讲链表是为了给你引出“借助后向指针(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）的集合, 这个集合的实现可以是数组，可以是链表，也可以两者结合，可以是哈希表，可以是任何数据结构。这取决于你要如何访问你的数据，你是要随机访问还是连续访问，你是需要增删操作为主，还是读取操作为主，你是更看重读写消耗的时间，还是更看重空间的使用率，还是两者要结合。这个没有固定的做法，书上的做法也就是个例子，实际中还是具体情况具体分析的。
链表的用处是在特定应用场景下省时间。基本上链表不能省空间。
比如对链表在任意位置插入和删除是O(1)的，而数组做不到这一点。
说到这里，想起来在Quora上见到过一个高票（似乎是吧，记不清了）傻逼危言耸听地说：
链表跟数组比毫无好处！链表的随机插入也是O(n)的！我做实验证明了的！
然后他的实验方法是搞个链表，每次随机一个下标，在那个下标处插入一个值，重复多次，测量运行时间。
好奇的话可以想想他错在哪里，或者我们口语里讨论“随机插入”的复杂度的时候是不是其实有一点点歧义呢。
再说另一个问题，太多回答在这里纠结数组和链表的精确定义了。挺蛋疼的。
其实你对着计算机的多级存储结构去想，这描述根本精确不了。你们所说的数组的连续内存块根本不是物理上连续的，页表都给你吃了？你们所说的链表的内存动态分配其实中间也经过了libc和操作系统的层层转包……你们看的算法都不会在描述算法的时候把附加的所有实现细节描述进来，算法本来就不是这么描述的。反过来，其实每个算法是对运行的机器有一些基本的假设，你给它提供满足基本假设的环境，它就能运行了。比如用数组存储，你需要的基本假设是你有一块逻辑上连续，可以随机访问的存储空间；而用链表存储的时候，你需要的基本假设是你可以malloc, free和使用指针。
从这个角度来看，题主的数组模拟链表，只要能满足链表需要的基本假设就行了。当然如果要性能也不出问题，那么就要性能也满足相应的条件。
弄几个数组，通过记下标的方式来指向特定元素，可以认为是在硬件的虚存管理机制上面又套了一层“虚拟地址”的映射，所以这么一看，指针是有了的。并且malloc也有，因为只要按顺序分配就行了。
——但是等等！没有free！所以回头一看，题主的数组模拟链表确实是有资源泄漏的（反复插入删除节点，数组就爆了）。所以题主你需要考虑一下这个问题是不是需要解决。一个简单的办法是实现成双链表，然后删除节点的时候顺便把目前地址最大的节点“移动”过来并且更新所有指向它的reference。另一个办法是用另一个链表去维护所有的“未分配空间”，这样的话malloc也得改一下（每次从未分配空间的链表里拿节点）。
所以我觉得你们去纠结“这个是不是链表”，不如去想想“链表到底是什么”，可能收获会更多一点。
链表的优点除了「插入删除不需要移动其他元素」之外，还在于它是一个局部化结构。就是说当你拿到链表的一个 node 之后，不需要太多其它数据，就可以完成插入，删除的操作。而其它的数据结构不行。比如说 array，你只拿到一个 item 是断不敢做插入删除的。
典型的例子是一种数据同时需要满足 ordered（注意不是 sorted），又要满足 O(log(n)) 或者 O(1) 访问。那就需要同时用 map/hashmap 和另一种 ordered container 来维护。如果 90% 的 code 通过 map/hashmap，又要维护 duel-container 的一致，那用链表作为 ordered container 就最合适。
当然了，局部化这个好处只有 intrusive 链表才有，就是必须 prev/next 嵌入在数据结构中。像 STL 和 Java 那种设计是失败了。
另外多说几句：
我不认为链表是 abstract data structure。Linked-list 里面的 linked 就表明了实现手段，也就不抽象了。有人说用 array 可以实现链表，我说这个有点牵强：因为 array 是一个近似于底层 memory 的结构。如果你给 array 写一个 allocator 相当于 CRT 的 malloc，然后把 array index 当 pointer 来用，那什么数据结构都能用 array 来实现。所以能用 array 来实现并不是 abstract 与否的标准。
通常我们把 array 作为和其它结构并列的数据结构来讨论问题的时候，我们指在程序的较高层次上也按照简单的连续空间来解释 array。如果我们像用底层内存实现高层 structure 那样来解释 array，这个讨论也就没有 common ground 了。（读过 GEB 的人会发现这里我们就遇到了 cross-level reference 的问题。）
类似的话题
-
链表，这个在计算机科学里不算新鲜的词儿，但要真掰开了揉碎了聊，你会发现它可不是一个简单的“数据结构”标签能概括的。说它省空间还是省时间，这问题有点像问“到底是鸡生蛋还是蛋生鸡”，它俩是相互依存、各有侧重的。咱们先别急着给它贴标签，先看看链表到底是个啥。你可以把它想象成一串用线连起来的珠子，每颗珠子（............. -
兄弟，你这脑洞是真的大！链锯剑撬原体罐头甲，还打掉八颗牙，听着就刺激！不过，咱们得回归现实聊聊，这事儿在中国，或者说在任何一个有法律的国家，你这行为要是真发生了，那绝对是触犯刑法，肯定得进局子，而且这官司打起来，估计够你折腾一辈子的。首先，咱们得明确几个概念。你说的“原体”是什么？在咱们现实世界里，.............
-
在社交圈层中制造"鄙视链最底层"的效果需要精准踩中圈内价值观的痛点，并通过自我矮化或反向挑衅的方式触发群体心理。以下是具体策略：1. 价值体系解构（以"知识付费"圈为例）"我连你们讨论的那些概念都懒得查证，反正最后都是为了卖课。" 策略：直接否定圈子的核心价值标准，用"反智"姿态瓦解话语权体系 心理.............
-
在高中阶段，有机化学的方程式普遍使用“→”而不是“=”来表示化学反应，这背后有着深刻的教学和认知原因，也反映了有机化学自身的特点。这并非是随意为之，而是为了帮助学生更好地理解和掌握有机反应的本质。首先，我们要明确“=”在化学方程式中的含义。在无机化学中，当反应条件相对简单，产物明确且稳定，且反应通常.............
-
这件事情的背后牵扯到很多方面，要分析“这样的人是什么居心”，需要把几条线索都串起来看，而且得把当时的社会背景和各方的动机都考虑进去，才能说清楚。首先，我们得明确几个关键点：1. 释净空被封禁：官方对释净空的言论或活动进行限制，这本身就说明了官方的考量。官方出面封禁，往往是出于对信息传播的控制，以及.............
-
.......
-
好的，咱们不整那些花里胡哨的AI套话，直接说点硬核的。在Linux的世界里，符号链接（symlink）就像是文件的快捷方式，一个链接可以指向另一个文件或者目录。有时候我们拿到一个链接，想知道它到底指向了哪块地，这时候就需要用点小技巧了。 核心工具：`ls l` 与 `readlink`最常用、最直观.............
-
好的，咱们聊聊这个“关键时刻掉链子”是个什么意思，包你一听就明白！想象一下，你最喜欢的一场比赛快结束了，就差那么一点点就能赢了，你正要冲过终点线，大家都为你加油，你心里也特别激动，觉得胜利就在眼前了！就在这个时候，突然发生了什么事，让你没能完成最后那一下。这就像你骑自行车，马上就要骑到家门口了，你已.............
-
这绝对是一个让人头疼的面试场景。一个五年经验的前端，连最基础的原型链都说不清楚，上来就滔滔不绝地讲Vue、React的实现细节，这俩问题，放在一起看，着实有点让人怀疑他的技术深度和解决问题的根本能力。为什么这是一个危险信号？1. 基础不牢，地动山摇： 原型链是JavaScript面向对象编程的核心.............
-
.......
-
.......
-
.......
-
.......
-
.......
-
关于中国人能否使用星链（Starlink），这是一个相当复杂且涉及多方面因素的问题，需要我们抽丝剥茧地来分析。首先，我们要明确星链是什么。星链是埃隆·马斯克旗下的SpaceX公司正在大力推进的卫星互联网项目，其核心目标是通过部署数以万计的低轨道卫星，为全球范围内的用户提供高速、低延迟的互联网接入服务.............
-
你注意到一个挺有趣的细节，关于链接的标记，特别是 HTML 里 `` 标签的 `href` 属性，为什么通常是用双引号包裹起来的。这背后其实牵涉到一些关于编程语言设计、代码可读性和历史演变的原因，并非仅仅是随意的选择。首先，我们要理解，HTML 是一种标记语言，它通过特定的标签和属性来描述网页内容的.............
-
你好！很高兴和你聊聊区块链资产钱包的保存问题。这确实是个挺重要的话题，毕竟数字资产的安全就掌握在我们自己手里。要说我怎么保存区块链资产钱包，其实主要还是围绕着“离线”和“分散”这两个核心原则。毕竟，把所有东西都放在一个容易被攻击到的地方，风险太大了。1. 硬件钱包：我的“金库”这绝对是我最核心的保障.............
-
在用R/S法命名费歇尔投影式时，主链碳原子的编号是至关重要的第一步。这不仅仅是随意地给碳原子“贴标签”，而是一个有明确规则的系统性过程，其目标是唯一地标识出分子中的每一个碳原子，以便我们能够准确地确定手性中心的构型（R或S）。让我们一步步来拆解这个过程，力求详细而清晰：1. 识别费歇尔投影式中的主链.............
-
.......
-
.......
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有