求职面试常见问题：数组与链表
链表和数组是两种常见的线性数据结构，主要区别如下：
1. 存储方式
-
数组：元素在内存中连续存储，通过索引直接计算地址，支持随机访问（时间复杂度O(1)）。
-
链表：元素以节点形式非连续存储，每个节点包含数据和指向下一个节点的指针，访问需从头遍历（时间复杂度O(n)）。
2. 大小灵活性
-
数组：固定大小，初始化后需重新分配内存才能扩展（如动态数组通过扩容实现，但成本较高）。
-
链表：动态扩展，增删节点仅需调整指针，无需预先确定大小。
3. 操作复杂度
-
插入/删除：
-
数组在中间操作需移动元素，时间复杂度O(n)；链表在已知位置时仅调整指针，时间复杂度O(1)。
-
数组尾部操作（若有空间）为O(1)；链表尾部操作若无尾指针需O(n)遍历。
-
-
访问：数组随机访问O(1)，链表需遍历O(n)。
4. 内存分配
-
数组：需连续内存空间，大数据量时可能分配失败。
-
链表：节点可分散存储，利用碎片化内存，空间利用率更灵活。
5. 空间开销
-
数组：仅存储数据，无额外开销。
-
链表：每个节点需额外空间存储指针（单链表1个，双向链表2个），数据较小时空间效率低。
6. 缓存性能
-
数组：连续内存利于缓存预加载，访问相邻元素速度快。
-
链表：节点分散导致缓存命中率低，访问效率可能下降。
7. 应用场景
-
数组：适合频繁随机访问、数据量固定或需高效缓存的场景（如排序、矩阵运算）。
-
链表：适合频繁增删、数据量变化大的场景（如队列、栈、图邻接表）。
总结
数组以快速访问和内存紧凑见长，链表以动态操作和灵活内存占优，选择取决于具体需求。