关于数据结构链表的问题请教

链表对于顺序表真正的优势是O1的任意插入和任意删除， 不然它作为一个缓存不友好的数据结构几乎都不如顺序表好用。 如果需要对列表进行大量的分割和合并操作或者是需要无锁并发可以考虑链表。

对于动态扩容顺序表重新内存分配的代价， 其实对于绝大多数的使用场景， Vector的容量是可以提前预测的， 提前开辟好足够容量的Vector即可， 如果说无法预测Vector的容量， 而且扩容发生的非常频繁的话， 那么链表确实是要更加节省性能一点。
链表节省内存空间的问题比较复杂， 一般顺序表扩容是倍增， 最坏的情况就是顺序表一半都是空的， 但是一般的Vector可能也就几个指针大小的浪费， 链表本身也有浪费， 单向浪费一个指针， 双向浪费两个指针， 只有节点的数据大小远大于指针的大小时指针的浪费才微不足道， 但是如果链表的数据元素小而且数量多空间浪费也是非常可观的， 除此之外这个还与链表节点有没有及时地分配和回收有关。
对于99%链表的场景来说可以用Vector来替代， 剩下1%中99%的场景可以用Deque， 它们具有更少的内存分配次数， 更低的内存占用， 支持随机访问而且是缓存友好的， 适用于绝大多数的场景。

如果不是反复需要插拔，链表这个结构就是完全不如顺序表

貌似主要是扩容很麻烦。据说实际的扩容很多时候不是在原位扩容的，因为可能原位后续已经没有那么多连续空间，他是在其他地方找一块连续且长度满足扩容后的长度的空间，把原来的空间复制过去，然后一开始的空间回收。很麻烦。如果频繁扩容复制来复制去特别麻烦，如果一开始申请特别多又浪费。。

用链表不一定节约空间

准确来说链表是方便插入和删除，至于节约空间有点扯淡，比如某个链表，一个节点不仅要保存数据还有保存一个指针。

如果我理解的没错的话 顺序数组 链表没有特别明确的鸿沟，也许可以从几个方面考虑吧：
1 元素是不是严格同构/同类型？
2 元素是否需要存储于连续空间，链表也可以存储在连续空间，数组在逻辑上也不是必须是连续空间，使用首地址偏移量跳转还是直接内存地址跳转
3 CRUD更在意哪一个
4 有没有多线程/原子化需求，倾向使用引用还是拷贝
5 元素预期数量/内存占用是多大，连续空间扩容是否会造成性能问题或者oom
6 需求倾向于顺序序列化还是索引化

不会吧，链表哪里要频繁扩容啊，链表前面申请的都不用动他们，加新元素的话只需要为最新那个申请一个单位就OK，然后只需要用指针把新元素和原本的末尾元素确认好他们两个的相对位置就可以。顺序表那种频繁扩容他是每次扩容，如果原位置后续的连续空闲空间不足，都要复制全部元素出去，主要是连续，连续这个条件不好办。链表不需要连续的，每次新来一个，安排一个零散空闲的空间就好，节点之间的连接的指针就像牵引线一样是用来确认相对位置的。

所以说，我的看法就是，一开始已经大概知道多少个元素的，或者知道最大大概多少的，这样只需要一个maxsize之类的预处理标识符就可以，这样子顺序表还是挺省事的，这样完美避开最麻烦的扩容时候可能带来的复制的麻烦。如果是哪种任意数量的元素都有可能的，那就整个链表，因为没办法说maxsize大概多少，有多少人用就申请多少个元素，一个不用了那就还一个元素的空间。

没人规定链表必须每次都是一个一个的malloc，你完全可以先malloc一个预估的大空间然后直接用数组的方式分配链表

看使用情况的，比如使用是一个班为单位，那么用户数量基本预留那个班人数多两三个可能差不多了，这种顺序表完全可以避免realloc，预留的浪费也就两三元素的空位。比如使用情况是无论多少人同时使用都应该尽量支持，那么就适合链表。无论是扩容时候的频繁复制，还是闲置一倍左右的元素的空间，都是蛮大的问题

linux栈有默认8mb，windows栈1mb，栈是来解决程序运行问题的，不是用来存放数据的

连续push_back 65536次，你可以看看不同分配策略时间差距有多小（不同测试波动都比这段时间大）