面试题：Rust中Vec和LinkedList在内存布局上的区别

内存布局差异

Vec（向量）：
- 连续存储：Vec在内存中是连续存储元素的。它类似于C++ 中的std::vector或Java中的ArrayList。当创建一个Vec时，它会在堆上分配一块连续的内存空间来存储所有的元素。例如，如果Vec存储的是i32类型的元素，假设每个i32占用4字节，若Vec中有10个元素，那么它会分配40字节的连续内存空间（不考虑其他元数据开销）。
- 元数据：Vec有三个主要的元数据字段，分别是指向数据存储起始位置的指针、当前元素数量（长度）以及分配的容量（可容纳元素的最大数量）。这三个元数据通常总共占用24字节（在64位系统上，指针8字节，usize类型的长度和容量各8字节）。
LinkedList（链表）：
- 非连续存储：LinkedList的元素在内存中是非连续存储的。每个元素封装在一个节点中，节点除了存储实际的数据外，还包含指向前一个节点和后一个节点的指针（双向链表）。在64位系统上，如果存储i32类型的数据，每个节点可能占用16字节（假设i32占4字节，两个指针各占8字节）。这些节点在堆上分散分配，通过指针相互连接。
- 元数据：LinkedList的元数据相对简单，主要包含指向链表头部和尾部节点的指针，在64位系统上总共占用16字节（两个指针各8字节）。

性能影响

访问性能：
- Vec：
  - 随机访问高效：由于Vec的元素在内存中连续存储，可以通过索引直接计算出元素的内存地址，时间复杂度为$O(1)$。例如，let value = my_vec[index];，这种方式可以快速定位到所需元素。
  - 顺序访问也高效：在缓存机制下，顺序访问Vec的元素时，由于内存连续，后续元素很可能已经被加载到缓存中，从而减少内存访问次数，提高访问效率。
- LinkedList：
  - 随机访问低效：LinkedList要访问第n个元素，需要从链表头部或尾部开始，通过指针逐个遍历节点，时间复杂度为$O(n)$。例如，要获取链表中第10个元素，需要遍历10个节点才能找到。
  - 顺序访问相对高效：顺序访问链表时，虽然不需要像随机访问那样从头开始，但由于节点在内存中不连续，缓存命中率较低，相比Vec在顺序访问上性能稍逊一筹。
插入和删除性能：
- Vec：
  - 中间插入/删除低效：在Vec中间插入或删除元素时，需要移动插入/删除位置之后的所有元素，时间复杂度为$O(n)$。例如，在Vec的第k个位置插入元素，需要将第k到n - 1个元素向后移动一个位置。
  - 尾部插入/删除高效：在Vec尾部插入或删除元素，时间复杂度为$O(1)$，因为不需要移动其他元素，只需要更新长度和可能的容量（如果容量不足需要重新分配内存）。
- LinkedList：
  - 中间插入/删除高效：在LinkedList中间插入或删除元素时，只需要修改相邻节点的指针，时间复杂度为$O(1)$。例如，在链表中某个节点A之后插入节点B，只需要修改A的后继指针和B的前驱指针。
  - 尾部插入/删除也高效：在链表尾部插入或删除元素同样只需要修改指针，时间复杂度为$O(1)$。
内存使用性能：
- Vec：
  - 内存紧凑：由于连续存储元素，Vec在内存使用上相对紧凑，没有额外的指针开销（除了元数据指针）。但如果预先分配的容量过大，可能会造成内存浪费。
  - 重新分配开销：当Vec的容量不足时，会重新分配内存，将原来的数据复制到新的内存位置，这会带来一定的性能开销。
- LinkedList：
  - 内存碎片化：由于节点分散存储，LinkedList可能会导致内存碎片化，特别是在频繁插入和删除节点的情况下。每个节点的指针也会占用额外的内存空间。
  - 无容量问题：LinkedList不存在像Vec那样的容量不足需要重新分配内存的问题，每次插入节点只需在堆上分配一个新的节点空间。

星途面试题库

面试题：Rust中Vec和LinkedList在内存布局上的区别

知识考点

面试题答案

内存布局差异

性能影响