面试题：Rust中Vec与LinkedList底层实现对性能的影响

Vec：
- 连续内存：Vec在内存中以连续的方式存储元素。这意味着所有元素紧密排列在一起，就像数组一样。例如，如果Vec存储i32类型的元素，每个元素占用4个字节，若有5个元素，它们会依次占用20个连续字节的内存空间。
- 结构组成：Vec包含一个指向堆上内存块的指针、当前容量（capacity）和元素数量（len）。容量表示当前分配的内存能容纳多少个元素，而数量表示实际存储的元素个数。
LinkedList：
- 非连续内存：LinkedList的每个节点在内存中是分散存储的。每个节点包含数据和指向前一个节点（前驱）和后一个节点（后继）的指针。例如，对于存储i32的LinkedList，每个节点除了4字节的i32数据外，还需要额外的指针空间（在64位系统上通常为8字节）来存储前驱和后继指针。
- 结构组成：LinkedList整体由一个指向链表头部的指针和一个指向链表尾部的指针组成，每个节点通过指针相互连接形成链表结构。

Vec：
- 随机访问：由于元素在内存中连续存储，Vec支持高效的随机访问。可以通过索引直接计算出元素在内存中的位置，时间复杂度为O(1)。例如，vec[index]操作可以快速定位到对应的元素。
- 边界检查：在Rust中，Vec的索引访问会进行边界检查，确保索引在有效范围内，这在一定程度上会增加运行时开销，但保证了安全性。
LinkedList：
- 顺序访问：LinkedList只能顺序访问元素，要访问第n个元素，需要从链表头部（或尾部）开始，依次遍历n个节点，时间复杂度为O(n)。例如，要获取链表中第10个元素，需要从头节点开始，通过指针依次移动9次才能到达目标节点。
- 无边界检查开销：因为不存在像Vec那样的索引概念，所以LinkedList在访问元素时没有边界检查的开销。

Vec：
- 连续迭代：Vec的迭代器利用其连续内存布局的优势，迭代时可以直接按顺序访问内存中的元素，非常高效。迭代器内部维护一个指向当前元素的指针，每次迭代通过指针偏移移动到下一个元素，时间复杂度为O(1) 。
- 缓存友好：由于元素连续存储，在迭代过程中对CPU缓存利用率高，减少了缓存未命中的次数，提高了性能。
LinkedList：
- 链式迭代：LinkedList的迭代器通过跟随节点间的指针来遍历链表。每次迭代都需要从当前节点获取下一个节点的指针，然后移动到下一个节点，时间复杂度为O(1) 。
- 缓存不友好：由于节点在内存中分散存储，迭代过程中频繁的内存跳转容易导致缓存未命中，降低了CPU缓存的利用率，性能相对较低。

Vec：
- 频繁插入/删除中间元素：当需要频繁在Vec中间插入或删除元素时，由于其连续内存布局，插入或删除操作后，后续元素都需要移动，时间复杂度为O(n)。例如，在长度为1000的Vec中间位置插入元素，大约需要移动500个元素。这种情况下，Vec的性能会显著下降。
- 内存重分配：当Vec的元素数量超过其当前容量时，会进行内存重分配。这涉及到在堆上重新分配更大的内存块，将原有元素复制到新内存块，然后释放旧内存块，时间复杂度为O(n)。如果频繁发生内存重分配，性能会受到很大影响。
LinkedList：
- 随机访问大量元素：如前所述，LinkedList顺序访问元素高效，但如果需要频繁随机访问大量元素，由于每次访问都要从头（或尾）开始遍历，时间复杂度为O(n)，性能会非常差。例如，要随机访问链表中1000个不同位置的元素，需要多次从头遍历链表，开销巨大。
- 链表过长：链表每个节点除了存储数据还需要额外的指针空间，链表过长会导致大量的内存碎片化，增加内存管理的开销，同时也会降低缓存利用率，进一步影响性能。

星途面试题库