数组和链表是两种常见的数据结构,它们在读取、插入、删除操作上有显著差异,下面详细说明:
1. 读取(访问)操作
-
数组:
数组是连续的内存空间,元素按索引(下标)存储,因此可以通过索引直接访问任意位置的元素,时间复杂度为 O(1)(常数时间)。例如,arr[5]
可以直接定位到第6个元素。 -
链表:
链表的元素(节点)分散存储在内存中,通过指针中的指针针(指针接)连接。要访问第n个元素,必须从表头开始依次遍历前n-1个节点,时间复杂度为 O(n)(线性时间)。
2. 插入操作
-
数组:
- 若在末尾插入,时间复杂度为 O(1)(直接追加)。
- 若在中间或头部插入,需要移动插入位置后的所有元素以腾出空间,时间复杂度为 O(n)(元素越多,移动成本越高)。
- 此外,数组容量固定(静态数组),满员时插入需要重新分配更大的内存并复制所有元素,成本更高。
-
链表:
插入时只需修改相邻节点的指针,无需移动其他元素,时间复杂度为 O(1)(前提是已定位到插入位置)。例如,在节点A和节点B之间插入节点C,只需将A的指针指向C,C的指针指向B即可。
3. 删除操作
-
数组:
- 若删除末尾元素,时间复杂度为 O(1)。
- 若删除中间或头部元素,需要移动删除位置后的所有元素以填补空缺,时间复杂度为 O(n)。
-
链表:
删除时只需修改相邻节点的指针(例如,删除节点B时,将A的指针直接指向C),无需移动其他元素,时间复杂度为 O(1)(前提是已定位到待删除节点的前驱节点)。
4. 查找是否等同于读取?
不完全等同:
- 读取 通常指“根据索引/位置获取元素”(如数组的
arr[i]
、链表的第i个节点)。 - 查找 通常指“根据元素的值找到其位置”,需要遍历数据结构(除非是有序数组可二分查找):
- 数组查找:顺序遍历为 O(n),有序数组二分查找为 O(log n)。
- 链表查找:只能顺序遍历,时间复杂度为 O(n)。
总结
操作 | 数组(平均情况) | 链表(平均情况 |
---|---|---|
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |
查找 | O(n) | O(n) |
数组适合频繁读取、元素数量固定的场景;链表适合频繁插入/删除、元素数量动态变化的场景。