2.15、数组和链表的区别

• • 数组
  在内存中是连续分配的一块空间，所有元素紧密排列，支持通过索引随机访问，时间复杂度为 O(1)。这种连续性带来了良好的缓存局部性，访问效率高。
  • • 在 C++ 中，数组的大小通常在编译时或初始化时确定（静态数组或动态数组，如 std::array 或原生数组）。
• • 链表
  由一系列节点组成，每个节点包含数据域和指针域，节点在内存中不必连续，通过指针将节点串联起来。链表的内存是动态分配的，大小可以根据需求在运行时自由扩展或收缩。
  • • 在 C++ 中，链表节点通常通过 new 动态分配内存，节点间通过指针（如 std::shared_ptr 或原始指针）连接。

访问效率

• • 数组
  支持基于索引的直接访问，利用指针偏移计算即可定位元素，访问速度快且缓存友好（连续内存块利于 CPU 缓存预取）。
• • 链表
  访问必须从头节点开始逐节点遍历，访问特定位置元素的时间复杂度为 O(n)。由于节点在内存中分散存储，缓存命中率低，访问效率较差。

插入和删除操作

• • 数组
  插入或删除元素时（尤其是在中间位置），需要移动大量元素以保持内存连续性，时间复杂度为 O(n)。
  • • 若数组容量不足，动态数组（如 std::vector）还需重新分配更大内存并复制数据，代价较高。
• • 链表
  插入和删除操作只需调整相关节点的指针，时间复杂度为 O(1)（前提是已定位到操作节点，否则定位仍需 O(n) 时间）。
  • • 链表天然支持动态扩展，插入删除灵活高效，无需移动其他元素。

内存利用和开销

• • 数组
  由于内存连续，空间利用率高，但大小固定或扩展时需要重新分配，可能导致空间浪费（预分配过大）或频繁复制（动态扩容）。
• • 链表
  每个节点除了存储数据外，还需额外存储指针（如指向下一节点的地址），导致每个元素的内存开销更大。
  • • 节点分散存储可能导致内存碎片，但支持动态增长，内存利用更灵活（按需分配节点）。

应用场景建议

• • 数组适合场景
  • • 需要频繁随机访问（如查找、读取操作）。
  • • 元素数量相对固定或变化不大（如数据量已知的缓冲区）。
  • • 对缓存友好性要求高的场景（如高性能计算、底层算法优化）。
• • 链表适合场景
  • • 插入和删除操作频繁（如实时数据更新、消息队列）。
  • • 元素数量动态变化大（如动态集合、数据流式处理）。
  • • 对内存连续性要求不高，更关注动态扩展灵活性的场景（如实现栈、队列、树结构等）。

总结对比表

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）