为什么部分应用场景优先选用链表而非数组？多项式大数存储应如何选型？

1. 为什么部分场景下链表比数组更受青睐 #

链表的核心优势体现在非随机位置的增删操作效率上，和数组对比：

• 数组如果要在中间位置插入/删除元素，需要把目标位置之后的所有元素整体移动，时间复杂度是O(n)，如果数组长度很大，这个开销会非常高
• 链表只需要修改目标位置前后节点的指针指向即可完成增删，不需要挪动其他元素，时间复杂度是O(1)（前提是已经拿到了目标位置的节点指针）
• 另外链表不需要预先申请整块连续内存，内存利用率更高，不会出现数组预申请空间闲置、或者扩容时需要拷贝整组数据的问题

2. 能不能通过malloc申请连续内存，用空字符标记末尾模拟类链表的存储？ #

技术上完全可以实现，这种本质上就是手动管理的动态数组，C语言标准库没有内置动态数组，很多开发者自己实现的动态数组就是类似的逻辑：预申请一块连续内存，记录已使用长度/剩余容量，不够的时候再realloc扩容，也可以用特殊标记（比如你说的空字符，或者自定义的哨兵值）标记元素末尾。

3. 为什么多项式项、超大数各位存储不推荐用上述连续内存方案？ #

不是不能用，是这类场景下连续内存方案的缺点会被放大，不如链表适配性高：

• 这类场景的增删操作非常频繁：比如多项式加减乘运算时会频繁新增/删除某一指数的项，超大数运算时会频繁在高位进位加位、或者借位删位，用连续内存的话每次操作都要移动大量元素，性能损耗远高于链表
• 元素数量波动范围极大：比如两个1000位的超大数相乘可能得到2000位的结果，多项式相乘后项数可能是原来的数倍，如果用连续内存，频繁的扩容、数据拷贝开销非常高，还容易出现内存碎片化问题
• 哨兵标记的局限性：如果存储的元素本身就包含你用来当哨兵的值（比如超大数的某一位就是0，多项式的系数就是0），你就没法用这个值来判断列表末尾了，需要额外维护长度变量，反而增加了逻辑复杂度

内容的提问来源于stack exchange，提问作者Zohaib Hamdule