C++ 链表和数组有什么区别 ？
参考答案：
C++ 中的链表和数组是两种不同的数据结构，它们有各自的特点和适用场景。以下是它们之间的主要区别：
-
存储方式：
- 数组：数组是在内存中连续分配的一块空间，用于存储相同类型的数据。数组的元素在内存中是紧密排列的，可以通过索引直接访问。
- 链表：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表在内存中的存储不是连续的，节点可以分散在内存的不同位置。
-
访问方式：
- 数组：数组可以通过索引直接访问任何元素，访问时间复杂度为 O(1)。
- 链表：链表需要从头节点开始，逐个遍历节点以访问特定元素。访问链表中的某个元素的时间复杂度为 O(n)，其中 n 是从头节点到目标节点的距离。
-
插入和删除操作：
- 数组：在数组中插入或删除元素需要移动大量元素以保持连续性，因此时间复杂度较高，为 O(n)。
- 链表：在链表中插入或删除元素只需修改指针的指向，不需要移动元素。在已知位置插入或删除元素的时间复杂度为 O(1)。
-
空间利用率：
- 数组：数组的空间利用率较高，因为它们在内存中连续分配，没有额外的空间开销。
- 链表：链表中的每个节点都包含数据和指向下一个节点的指针，因此空间利用率相对较低。
-
动态性：
- 数组：数组的大小在创建时确定，不能动态调整。如果需要扩展数组大小，通常需要创建一个新的数组，将旧数组的内容复制到新数组中，然后释放旧数组的内存。
- 链表：链表可以动态地添加和删除节点，不需要预先确定大小。这使得链表在处理动态数据集合时更为灵活。
总之，数组和链表各有优缺点，适用于不同的场景。在选择数据结构时，需要根据具体需求和性能要求来权衡。