C语言：链表和数组有什么区别

在 C 语言中，链表和数组有以下区别：

一、内存分配方式

1. 数组：

   • 数组在内存中是连续分配的一块空间。
   • 定义数组时，其大小必须在编译时确定，一旦确定后就不能再改变。例如 int arr[10]; 定义了一个包含 10 个整数的数组，这个数组在内存中占据连续的 40 个字节（假设整数占 4 个字节）。
   • 如果需要动态改变数组的大小，通常需要使用一些复杂的技巧，如重新分配更大的内存空间并复制原有数据。

2. 链表：

   • 链表中的节点可以分散在内存中的不同位置，通过指针连接起来。
   • 链表的大小可以在运行时动态地增加或减少，只需要在需要的时候分配新的节点空间或者释放不再使用的节点空间即可。

二、随机访问性能

1. 数组：

   • 可以通过下标直接访问任意元素，具有高效的随机访问性能。例如，访问数组中的第 n 个元素可以直接通过 arr[n] 的方式，时间复杂度为 O(1)。
   • 由于内存连续，CPU 缓存更容易命中，对于频繁访问的情况可能会有更好的性能表现。

2. 链表：

   • 要访问链表中的特定元素，必须从链表的头节点开始，逐个遍历节点，直到找到目标节点。因此，链表的随机访问性能较差，时间复杂度为 O(n)，其中 n 是链表的长度。

三、插入和删除操作

1. 数组：

   • 在数组中间插入或删除元素可能比较耗时。因为需要移动插入或删除位置后面的所有元素，以保持数组的连续性。如果插入或删除操作频繁，会导致性能下降。
   • 例如，在一个包含 n 个元素的数组中间插入一个元素，最坏情况下需要移动 n/2 个元素，时间复杂度为 O(n)。

2. 链表：

   • 在链表中插入或删除元素相对容易。只需要修改相关节点的指针即可，不需要移动其他元素。
   • 例如，在链表中间插入一个节点，只需要调整前后两个节点的指针指向新节点，时间复杂度为 O(1)。但是，如果需要找到插入或删除的位置，可能需要遍历链表，这部分时间复杂度为 O(n)。

四、内存使用效率

1. 数组：

   • 由于内存连续分配，可能会出现内存碎片的问题。特别是当数组大小动态变化时，频繁的重新分配可能导致内存碎片增多，降低内存使用效率。
   • 但是，如果数组的大小在编译时确定，并且能够充分利用分配的空间，那么内存使用效率可能会比较高。

2. 链表：

   • 链表的节点可以在需要的时候动态分配，不会产生内存碎片问题。但是，每个节点除了存储数据外，还需要额外的空间来存储指针，因此内存使用效率相对较低。

五、数据存储方式

1. 数组：

   • 适合存储相同类型的数据，可以使用下标直接访问元素。
   • 数组的元素在内存中是紧密排列的，对于存储大量连续的数据非常有效。

2. 链表：

   • 可以存储不同类型的数据，只要节点的数据部分能够容纳不同类型的数据即可。
   • 链表的节点可以根据需要灵活地存储各种数据结构，并且可以方便地进行动态扩展和收缩。